print2049. День Рагнарёк

printДень Рагнарёк

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вот и настал день Рагнарёк. Чудовищный волк Фенрир проглотил Солнце, погрузив тем самым мир во тьму, из глубин морей всплыл мировой змей Ёрмунгланд. К ним примкнул и огненный великан Сурт с пылающим мечом, и повелительница загробного царства Хель, и коварный бог огня Локи вместе с инеистыми великанами – хримтусами и ётунами. Из Хельхейма приплыл корабль мертвецов Нагльфар, а войско сына Муспельхейма проскакало по мосту Биврёст, при этом разрушив его.
Асгарда, Мидгарда, Йотунхейма и Муспельхейма больше нет, нет и страны гномов, и страны эльфов. Но высоко-высоко в небе, там, где раньше был Асгард, но только еще выше его, стояли младшие боги. Это были молчаливый Видара, храбрый Вали, могучие Магни и Моди и меткий Ульр – они остались живы. Вместе с ними Бальдр и Ход, которым удалось вырваться из царства Хель. За поясом у Магни молот его знаменитого отца. Молодые боги разговаривают друг с другом, вспоминая дела и подвиги минувших веков, и строят для себя новую страну, а под ними из мирового моря опять подымается земля. Она вся зеленая, она покрыта чудесными лесами, садами, пастбищами и нивами.
Двое людей пережили Рагнарёк. Огонь Сурта не коснулся их. Они были далеко в глухом лесу, придумывали как остановить этот ужас, а когда придумали, мир вновь стал зелен и прекрасен. Питались они утренними росами. Это были женщина и мужчина, Лив и Ливтрасир. Они вышли из леса и народили детей, которые, тоже народив детей, заселили землю.
Для того, чтобы остановить Рагнарёк, Лив и Литрасир должны хором произнести волшебное слово. Волшебное слово должно одинаково читаться как справа налево, так и слева направо. А также, когда Лив и Литрасир произносят волшебное слово, они должны произнести имя малоизвестного бога, способного остановить Рагнарёк. При этом они хотят, чтобы длина волшебного слова была как можно меньше.
Во входном файле дано имя бога, способного остановить Рагнарёк. Длина имени не превосходит `3*10^5` и состоит из строчных латинских букв.
Выведите минимальное по длине волшебное слово `t`, способное остановить Рагнарёк. Если таких слов несколько, то выведите любое.

Пример ввода 1

ab

Пример вывода 1

aba

Пример ввода 2

a

Пример вывода 2

a
Источник: neerc.ifmo.ru/school
loading