Задача 05B. Префиксные основы ≡

Условие

Пусть имеется формальный язык, слова которого представляют собой цепочки символов, составленные из отдельных неперекрывающихся подцепочек (морфов). Значения, которые способны принимать указанные морфы, образуют словарь базовых единиц (основ) исходного языка. При этом полагается, что никакие две основы не могут иметь общих префиксов.

Для заданного набора слов требуется определить список основ, разбивающих их на минимально возможное число морфов. Для каждой такой основы необходимо также посчитать, сколько раз она встречается в исходном тексте (в качестве значения какого-либо морфа).

Формат входного файла

В начале входного файла "input.txt" хранится натуральное число n. Далее следует набор из n слов, состоящих из цифр и букв латинского алфавита (регистр их написания неважен). При этом каждое слово располагается в отдельной строке.

Формат выходного файла

Выходной файл "output.txt" должен содержать все найденные основы (без повторений), приведенные к одному регистру и расположенные в лексикографическом порядке. Напротив каждой такой основы (через пробел) указывается число совпадающих с ней морфов.

Ограничения

Полагается, что длина отдельно взятого слова лежит в диапазоне от 1 до 5000.

0 < n ≤ 10⁵.

Размер входного файла не превосходит 10 МБ.

Примеры тестов

10
abcd11112345
y4141
abcd1111
abcdy
yyyy
abcdabcdabcd
A1111
A1111
11114141
AbcD

1111 5
2345 1
4141 2
a 9
bcd 7
y 6

10
111123abcd
y4141A
abcd1111
y4141a
abcdy
AbCdA
AbCd1111
abcd
A1111
aA

1111 4
23abcd 1
4141a 2
a 9
bcd 5
y 3