SPOJ in Gyumri

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

Входные данные

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

Выходные данные

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

Пример