Предположим, вам даны две строки \(a\) и \(b\). Вы можете применить следующую операцию любое количество раз: выбрать любую непрерывную подстроку \(a\) или \(b\) и отсортировать символы в ней в порядке неубывания. Пусть \(f(a, b)\) — минимальное количество операций, которое необходимо применить, чтобы сделать строки равными (или \(f(a, b) = 1337\), если невозможно сделать \(a\) и \(b\) равными с помощью этих операций).
Например:
- \(f(\text{ab}, \text{ab}) = 0\);
- \(f(\text{ba}, \text{ab}) = 1\) (за одну операцию мы можем отсортировать всю первую строку);
- \(f(\text{ebcda}, \text{ecdba}) = 1\) (за одну операцию мы можем отсортировать подстроку со \(2\)-го по \(4\)-й символ второй строки);
- \(f(\text{a}, \text{b}) = 1337\).
Вам задано \(n\) строк \(s_1, s_2, \dots, s_k\) одинаковой длины. Вычислите \(\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)\).
Выходные данные
Выведите одно целое число: \(\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
zzz
bac
abc
acb
|
4015
|
|
2
|
2
a
b
|
1337
|