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