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