Задача N. Палиндромная сортировка

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Для строки S = S1,~S2,~…,~Sm определим коэффициент ее палиндромности: q[S] = k / m, где k — максимальное число позиций i в которых выполняется условие: Si~=~Sm − i + 1.

Так, например, для строк "abcba" и "abba" коэффициент палиндромности равен 100%. В то время, как для строк "abdca" и "abca" — 60% и 50% соответственно.

Требуется выполнить сортировку заданного набора слов по убыванию коэффициентов их палиндромности.

При этом для слов, обладающих одинаковой палиндромностью, порядок следования должен быть сохранен.

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

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

При этом каждое такое слово располагается в отдельной строке.

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

Выходной файл "output.txt" должен содержать индексы исходных слов, расположенные в порядке их следования в отсортированном массиве.

При этом полагается, что нумерация слов начинается с нуля.

Ограничения

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

0 < n ≤ 5 ⋅ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10
76i3600c1
8r2xsdc44cdsxsr8
7q9wxw9q7
alf4dx3d3xdgfla
njuuiuiui0n
ierxx0es
s028338u0s
nac9ps4can
t44agihgh44t
3vtkbbkv3
2
1
3
6
8
4
7
9
5
0
2
10
15nuie40t04eiun51
l8320aa0138l
20qwzwq02
a
2e1ff1e2
4euee33e7ue4
e80t
6fesehtesif6
ml
i42iirptub
0
2
3
4
1
5
7
6
8
9

0.106s 0.020s 15