Description

回文串指一个字符串从前往后读和从后往前读完全一样，例如：abcba

算法星球的小明发明了一个字符串游戏：给定一个字符串，你可以将字符串中的任意两个字符改为'a'~'z'的其中一个字母（可以不改），并且保证该字符串最多经过两次修改一定可以成为一个回文串，但这样修改可能会形成非常多个不同的回文串，游戏要求输出字典序最小的回文串。

例如： ddbaa可以修改为ddbdd或者aabaa，但一定要输出aabaa，因为它的字典序最小。

Format

Input

一行字符串，保证全部由小写字母组成

Output

一行字符串，表示在满足限制的情况下字典序最小的回文串

Samples

ddbaa

aabaa

abcde

abcba

Limitation

对于测试点 1 − 3：字符串长度介于 [1, 10] 之间。

对于测试点 4 − 5：字符串长度介于 [1,300] 之间。

对于测试点 6 − 8：字符串长度介于 [1, 1000] 之间。

对于测试点 9 − 10：字符串长度介于 [1, 100000] 之间。