Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Бард Лютик сочинил новую балладу про подвиги своего друга Геральта и теперь хочет оценить, насколько она мелодична. Знакомый профессор с кафедры поэзии Оксенфуртского университета недавно вывел специальную формулу для оценки мелодичности, но для Лютика она слишком сложна. Помогите барду подсчитать мелодичность его нового шедевра.
Баллада состоит из строк, пронумерованных от `1` до `N` и содержащих только строчные буквы латинского алфавита. Две строки баллады назовем `k`-рифмованными, если их наибольший совпадающий суффикс имеет длину `k`. Например, строки `abcd` и `xxcd` являются `2`-рифмованными, но не являются `1`-рифмованными.
Мелодичность строки `S`, имеющей номер `i`, определяется так. Переберем все числа `k` от 1 до длины `S`, для каждого `k` выберем среди строк с номерами меньше `i` только `k`-рифмованные строки. Пусть таких строк было `cnt_k`, а индекс последней из них обозначим за `prev_k`. Тогда мелодичность строки равна сумме по всем `k` значений `k * prev_k * cnt_k` (пример вычисления приведен ниже).
Мелодичность баллады равна сумме мелодичности всех её строк. По тексту баллады подсчитайте её мелодичность.
В первой строке входных данных содержится единственное целое число `N` (`1 <= N <= 3 * 10^5`) — число строк в балладе.
Затем следует `N` строк, состоящих из строчных букв латинского алфавита — текст баллады. Общая длина текста не превосходит `3 * 10^5` символов.
Выведите единственное число — мелодичность баллады Лютика, подсчитанной согласно описанной выше процедуре.
```sample Пример ввода
5
abcd
aad
cd
bcd
bcd
```
```sample Пример вывода
48
```
Пояснение к примеру 1:
* мелодичность строки 1 равна 0;
* мелодичность строки 2 равна `1 * 1 * 1` (единственная `1`-рифмованная строка с номером `1`);
* мелодичность строки 3 равна `1 * 2 * 1` (`1`-рифмованная строка с номером `2`) `+` `2 * 1 * 1` (`2`- рифмованная строка с номером `1`);
* мелодичность строки 4 равна `1 * 2 * 1` (`1`-рифмованная строка с номером `2`) `+` `2 * 3 * 1` (`2`-рифмованная строка с номером `3`) `+` `3 * 1 * 1` (`3`-рифмованная строка с номером `1`);
* мелодичность строки 5 равна `1 * 2 * 1 + 2 * 3 * 1 + 3 * 4 * 2` (пара `3`-рифмованных строк, последняя из которых имеет номер `4`).
Общая мелодичность баллады равна `0 + 1 + 4 + 11 + 32 = 48`.
```sample Пример ввода
6
whenahumblebard
gracedaridealong
withgeraltofrivia
alongcamethissong
tossacointoyourwitcher
tossacointoyourwitcher
```
```sample Пример вывода
116
```
Начало
Рабочее место участника
Бор