题目描述:

现在牛牛获得了一个字符串。牛牛想要使得这个字符串是回文串。 你可以将字符串中至多两个位置改为任意小写英文字符 $a$-$z$，牛牛希望你能帮他把这个字符串改成回文串。好心的牛牛向你保证，他给你的字符串一定可以经过至多两次修改就变成回文串，但是一个字符串可能会有很多的改法，牛牛担心你不会配置 $spj$，于是要求你输出字典序最小的回文串。

注：回文字符串是指一个字符串满足从前向后读和从后向前读完全相同。 例如字符串 $abcba$, $aaaa$, $acca$ 都是回文字符串。字符串 $abcd$, $acea$ 都不是回文字符串。

输入格式:

一行一个字符串。字符串仅由小写英文字符构成。

输出格式:

一行一个在题目条件限制下所可以获得的字典序最小的回文字符串。

样例输入1

beeb

样例输出1

aeea

样例输入2

abcde

样例输出2

abcba

将 de 改为 ba 可以获得字典序最小的回文字符串。将 ab 改成 ed 虽然也可以构成回文串， 但不是字典序最小的

备注:

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

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

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

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