Make a superpalindrome

A palindrome is a string that reads the same forward and backward. For example, madam is madam read forward and madam read backward, so it is a palindrome. Among palindromes there are superpalindromes, defined recursively as follows.

1. Every superpalindrome is a palindrome.
2. Every string of length 1 is a superpalindrome.
3. If the length is even, split the string in half. The front half and the back half must both be superpalindromes.
4. If the length is odd, drop the middle character and split the rest in half. The front half and the back half must both be superpalindromes.

For example, in aa the front half and the back half are both the string a, which has length 1 and so is a superpalindrome. That makes aa a superpalindrome. By the same reasoning aaaa and aabaa are superpalindromes. In aabaa, dropping the middle b and splitting the rest leaves aa on both sides.

You are given a string of lowercase letters. Among the strings that consist of lowercase letters, have the same length as the given string, and come after it in lexicographic order, find the superpalindrome that comes first in lexicographic order.

The first line contains one string of lowercase letters. Its length is at least 2 and at most 100,000, and the string is not a superpalindrome.

Print the answer on the first line. It is the superpalindrome that comes first in lexicographic order among the strings that consist of lowercase letters, have the same length as the input, and come after the input in lexicographic order. The input is not a superpalindrome, so it cannot be the string made only of z, and an answer always exists.