Palindrome
A small publishing house decided to create an encyclopedia featuring all possible palindromes—texts that read the same forwards and backwards. Unfortunately, during the typesetting process, numerous errors occurred. To address this, they decided to automate the typesetting of palindromes and hired a team of programmers for the task.
The programmers efficiently generated all possible palindromes, sorted in alphabetical order. However, the director of the publishing house, a very astute individual, wanted to verify their work. Lacking programming knowledge and aiming to conserve time and resources, the director proposed a challenge: for a few given words, determine and print the last palindrome of the same length that does not exceed the given word in lexicographical order. Although this task is more complex than the original, the programmers must complete it to receive their payment.
Input
A single word composed of lowercase Latin letters, with a maximum length of 1000 characters.
Output
Print the required palindrome of the same length. If the input word is already a palindrome, print it unchanged.