22156번 - Ключ к шифру 다국어

Все те сотни лет, в течении которых существуют государства, границы и периодически возникающие конфликты между странами, существует и система шпионажа. Агент, нелегально или легально проживающий в одной стране, отправляет донесения, содержащие в себе государственную тайну, в другую страну. Способы передачи донесений непрерывно меняются. Сто лет назад это были бумажные письма, пятьдесят лет назад — радиограммы, сейчас же есть возможность отправить донесение даже по электронной почте. Однако, одна характерная черта всех донесений не изменилась и не изменится никогда — любое информационное сообщение можно перехватить. Чтобы застраховаться от такой возможности, донесения шифруются так, чтобы прочитать их мог только тот, кому они предназначены. При этом обычно используется некоторый ключ — сравнительно небольшая строка, часто не имеющая смысла, с помощью которой донесение можно расшифровать. А чтобы, в случае поимки агента, он не мог сообщить ключ заинтересованным лицам, каждому донесению соответствует свой ключ, который отправляется вместе с донесением, тоже зашифрованный, но не очень сложным способом. Вам предстоит научиться получать этот ключ по его зашифрованной версии для некоторого алгоритма шифрования.

Чтобы зашифровать непустой ключ s, агент сначала выбирает такую строку t, что строка s является префиксом строки t, а развернутая строка s — суффиксом строки t. При этом в строке t могут быть символы, не имеющие отношения к строке s. После этого слева к строке t дописывается некоторое случайное (возможно, нулевое) количество случайных символов, справа же дописывается точно такое же количество, возможно других, случайных символов. Теперь строка t представляет из себя зашифрованный ключ s.

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

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

Выведите n расшифрованных ключей, по одному на строке.