Make superpalindrome! Batch Compilation commands

펠린드롬을 아는가? 펠린드롬이란 문자열들 중에서 앞으로 읽는 것과 뒤로 읽는 것이 같은 문자열을 의미한다. 예를 들어 madam 의 경우 앞으로 읽어도 madam 이며 뒤로 읽어도 madam 이므로 펠린드롬인 것이다. 펠린드롬들 중에서도 슈퍼펠린드롬이 라는 것이 있는데, 슈퍼펠린드롬은 다음과 같이 재귀적으로 정의된다.

0. 슈퍼펠린드롬은 모두 펠린드롬이어야 한다.
1. 길이가 1 인 문자열은 모두 슈퍼펠린드롬이다.
2. 길이가 짝수인 경우 문자열을 절반으로 쪼갰을 때, 앞의 절반과 뒤의 절반이 모두 슈퍼펠린드롬이어야 한다.
3. 길이가 홀수인 경우 가장 중앙에 있는 문자를 제외하고 절반으로 쪼갰을 때, 앞의 절반과 뒤의 절반이 모두 슈퍼펠린드롬이어야 한다.

예를 들어 aa 의 경우 앞의 절반과 뒤의 절반이 모두 문자열 a 이며, 이는 길이가 1 이므로 슈퍼펠린드롬이다. 즉 aa 는 슈퍼펠린드롬인 것이다. 그러므로 aaaa 와 aabaa 도 슈퍼펠린드롬임을 알 수 있다. (aabaa 의 경우 가장 중앙의 b 를 제외하고 절반으로 쪼개면 앞의 절반과 뒤의 절반이 모두 aa 이므로 슈퍼펠린드롬인 것이다.)

알파벳 소문자로 이루어진 $L$자리의 문자열이 주어진다. 소문자로 이루어진 문자열들 중에 주어진 문자열 보다 사전순으로 뒤에 있고 길이가 같으면서 슈퍼펠린드롬인 문자열을 출력하는 프로그램을 작성하라.

입력 형식

첫 번째 줄에 문자열이 하나 주어진다. 이 문자열의 길이는 $2$ 이상 $100,000$ 이하이며, 이 문자열은 슈퍼펠린드롬이 아니다.

출력 형식

입력으로 주어진 문자열보다 사전순으로 뒤에 있으면서 알파벳 소문자로 이루어져 있고 길이가 같은 문자열들 중에 가장 사전 순으로 빠른 슈퍼펠린드롬을 출력한다.

입력

abaaca

출력

acaaca