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

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

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

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

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

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