Description

现在牛牛获得了一个字符串。牛牛想要使得这个字符串是回文串。

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

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

Input Format

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

Output Format

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

beeb

aeea

abcde

abcba

Hint

样例一说明 原来的字符串已经是回文字符串了。但它不是题目条件下可以取得的字典序最小的回文字符 串。将第一个位置和第四个位置改成 $a$ 就可以获得字典序更小的字符串。

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

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