eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Палиндром

Палиндром

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

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

Команда быстро справилась с задачей печати всех возможных палиндромов, упорядоченных по алфавиту, но директор издательства (большого ума человек) решил проверить их работу. Поскольку директор ничего не понимал в программировании и хотел сэкономить время и средства, он предложил несколько слов и попросил для каждого из них напечатать последний палиндром той же длины, который не превосходит в лексикографическом порядке заданное слово. Несмотря на то, что поставленная задача сложнее исходной, для получения зарплаты программистам придётся выполнить пожелание директора…

Вхідні дані

В единственной строке слово, состоящее из строчных латинских букв, длина слова не превышает 1000 букв.

Вихідні дані

В первой и единственной строке искомый палиндром той же длины. Если входное слово уже является палиндромом, то напечатать его же.

Приклад

Вхідні дані #1
asabayy
Вихідні дані #1
asabasa
Джерело ACM ICPC 2013-2014 NEERC Siberian Group