Statement is not available in English language
D. Близкие строки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим близость двух строк следующим образом: выделим у обоих строк наибольший общий префикс (совпадающие буквы в начале строк) и удалим его. Затем выделим наибольший общий суффикс у обеих строк (совпадающие буквы в конце строк) и тоже удалим его. Сумма длин удалённого префикса и суффикса будет равна близости этих строк.

К примеру, близость строк programming и pruning равна пяти: cначала удаляем наибольший общий префикс pr, затем удаляем наибольший общий суффикс ing. Сумма длин этих строк равна $$$2 + 3 = 5$$$. Также близость строк hse и hsehsehse равна трём, поскольку после удаления наибольшего общего префикса hse, длина наибольшего общего суффикса у пустой строки и hsehse равна нулю.

Дан набор из $$$n$$$ строк. Для каждой строки найдите ближайшую к ней из набора, исключая саму эту строку.

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

Первая строка входных данных содержит одно целое число $$$n$$$ $$$\ge$$$ 2 — число строк.

Каждая из следующих $$$n$$$ строк содержат одну строку из строчных букв латинского алфавита

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

В единственной строке выходных данных выведите $$$n$$$ чисел, разделённых пробелом — номера ближайших строк для каждой строки. Строки пронумерованы от 1 до $$$n$$$ в том порядке, в котором они перечисляются во входном файле.

Если возможных ответов несколько, выведите любой из них.

Система оценки

Тесты к задаче разделены на четыре группы. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов из предыдущих групп.

Обозначим за k как максимальную длину строки, а $$$S=\sum_{i = 1}^n |s_i|$$$ как суммарную длину всех строк. $$$(n \le 10^6, k \le 10^6, \le S \le 12 \cdot 10^5)$$$

ГруппаБаллыnkS
$$$1$$$15$$$n \le 2000$$$$$$k \le 100$$$$$$S \le 2 \cdot 10^5$$$
$$$2$$$25$$$n \le 10^6$$$$$$k \le 100$$$$$$S \le 10^6$$$
$$$3$$$40$$$n \le 10^6$$$$$$k \le 10^6$$$$$$S \le 10^6$$$
$$$4$$$20$$$n \le 10^6$$$$$$k \le 10^6$$$$$$S \le 12 \cdot 10^5$$$
Пример
Входные данные
6
pruning
problem
hse
algorithm
programming
hsehsehse
Выходные данные
5 5 6 2 1 3