Задача S3. Нормальная палиндромика

Автор:Жюри летних сборов, И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Палиндром — это строка, которая одинаково читается и в прямом, и в обратном порядке. Например, kazak — палиндром, а kazachka — нет. По данной строке S требуется найти такую кратчайшую (возможно, пустую) строку P, что строка S + P будет палиндромом.

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

Во входном файле содержится строка S, состоящая из маленьких латинских букв.

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

В выходной файл необходимо вывести строку P.

Ограничения

Длина исходной строки не превосходит 300000 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abcc
ba
2
abcd
cba

0.072s 0.016s 13