슈퍼펠린드롬 만들기

펠린드롬은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다. 예를 들어 madam은 앞으로 읽어도 madam이고 뒤로 읽어도 madam이므로 펠린드롬이다. 펠린드롬 중에서도 슈퍼펠린드롬이라는 것이 있는데, 슈퍼펠린드롬은 다음과 같이 재귀적으로 정의한다.

1. 슈퍼펠린드롬은 모두 펠린드롬이어야 한다.
2. 길이가 1인 문자열은 모두 슈퍼펠린드롬이다.
3. 길이가 짝수인 경우 문자열을 절반으로 쪼갰을 때, 앞의 절반과 뒤의 절반이 모두 슈퍼펠린드롬이어야 한다.
4. 길이가 홀수인 경우 가장 가운데 문자를 빼고 절반으로 쪼갰을 때, 앞의 절반과 뒤의 절반이 모두 슈퍼펠린드롬이어야 한다.

예를 들어 aa는 앞의 절반과 뒤의 절반이 모두 문자열 a이고 길이가 1이므로 슈퍼펠린드롬이다. 같은 이유로 aaaa와 aabaa도 슈퍼펠린드롬이다. aabaa는 가운데 b를 빼고 절반으로 쪼개면 앞의 절반과 뒤의 절반이 모두 aa이다.

알파벳 소문자로 이루어진 문자열이 주어진다. 알파벳 소문자로 이루어지고, 주어진 문자열과 길이가 같으며, 사전순으로 주어진 문자열보다 뒤에 오는 슈퍼펠린드롬 중에서 사전순으로 가장 앞선 것을 구하라.

첫째 줄에 알파벳 소문자로 이루어진 문자열이 하나 주어진다. 이 문자열의 길이는 2 이상 100,000 이하이고, 이 문자열은 슈퍼펠린드롬이 아니다.

첫째 줄에 답을 출력한다. 알파벳 소문자로 이루어지고, 입력으로 주어진 문자열과 길이가 같으며, 사전순으로 입력 문자열보다 뒤에 오는 슈퍼펠린드롬 중에서 사전순으로 가장 앞선 것이다. 입력 문자열은 슈퍼펠린드롬이 아니므로 z로만 이루어진 문자열일 수 없고, 따라서 답은 항상 존재한다.