F. Расстояние между строками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Предположим, вам даны две строки $$$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)$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество строк.

Затем следует $$$n$$$ строк, каждая строка содержит одну из строк $$$s_i$$$, состоящую из строчных латинских букв. $$$|s_1| = |s_2| = \ldots = |s_n|$$$ и $$$n \cdot |s_1| \le 2 \cdot 10^5$$$. Все заданные строки попарно различны.

Выходные данные

Выведите одно целое число: $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.

Примеры
Входные данные
4
zzz
bac
abc
acb
Выходные данные
4015
Входные данные
2
a
b
Выходные данные
1337