28564번 - Устрашающий палиндром 스페셜 저지다국어

Дети весь вечер ходили по домам и пугали прохожих. В какой-то момент это им надоело и они пошли пугать мистера Х.

Все знают, что мистер X очень боится палиндромов. Поэтому дети решили найти самый большой палиндром и показать его мистеру. К сожалению, за ночь фантазия у детей почти закончилась, и все что им оставалось --- это выписать слова с окружающих их рекламных баннеров и собрать палиндром из них.

Всего на улице расположено $n$ баннеров, надписи на всех баннерах имеют одинаковую длину $k$. Дети считают, что палиндром получится недостаточно устрашающий, если не использовать хотя бы одну надпись, поэтому они хотят составить палиндром, конкатенируя в некотором порядке все надписи на вывесках по одному разу.

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

В первой строке через пробел даны два целых числа $n$ и $k$ ($1 \leq n, k \leq 10^6$).

В следующих $n$ строках перечислены надписи на окружающих баннерах, по одной в строке. Каждая надпись имеет длину в точности $k$ и состоит исключительно из строчных букв латинского алфавита.

Гарантируется, что $n \cdot k \leq 10^7$.

Если устрашающий палиндром можно составить, выведите $n$ чисел, разделенных пробелами --- номера вывесок в том порядке, в котором их надо конкатенировать, чтобы получился палиндром. Каждое число от $1$ до $n$ должно присутствовать в выводе ровно один раз.

Если же палиндром составить нельзя, выведите единственное целое число $-1$.