题目描述

现在强哥获得了一个字符串。强哥想要使得这个字符串是回文串。（回文串是什么呢，就是正着读反着读都一样，比如上海自来水来自海上）
你可以将字符串中至多两个位置改为任意小写英文字符 𝑎−𝑧，强哥希望你能帮他把这个字 符串改成回文串。好心的强哥向你保证，他给你的字符串一定可以经过至多两次修改就变成 回文串，但是一个字符串可能会有很多的改法，强哥作为一个好心人，于是要求你输出 字典序最小的回文串。（强哥真是太善良了，呜呜呜呜呜呜呜呜）

回文串举例： abcba aaa
不是回文串的例子: qiangge

输入格式

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

输出格式

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

beeb

aeea

样例1解释： 原来的字符串已经是回文串了，但是不是要求的最小回文串。将第一个位置和第四个位置改成 𝑎 就可以获得字典序更小的字符串。

提示

对于测试点 1−3:字符串长度介于 [1,10] 之间。
对于测试点 4 − 5:字符串长度介于 [1,300] 之间。
对于测试点 6−8:字符串长度介于 [1,1000]之间
对于测试点 9−10:字符串长度介于 [1,100000] 之间。