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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

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

0 < n ≤ 5 ⋅ 10⁴

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

10
76i3600c1
8r2xsdc44cdsxsr8
7q9wxw9q7
alf4dx3d3xdgfla
njuuiuiui0n
ierxx0es
s028338u0s
nac9ps4can
t44agihgh44t
3vtkbbkv3

2
1
3
6
8
4
7
9
5
0

10
15nuie40t04eiun51
l8320aa0138l
20qwzwq02
a
2e1ff1e2
4euee33e7ue4
e80t
6fesehtesif6
ml
i42iirptub

0
2
3
4
1
5
7
6
8
9