题目内容

塔子哥是一个热衷于算法竞赛的程序员，他最近在参加一场名为“回文字符串”的比赛。比赛规则是给定一个字符串，要求将其修改为一个回文字符串，所修改的字符位置最多只能有两个，并且要求修改后的字符串字典序最小。

塔子哥在比赛中遇到了困难，不知道如何处理才能让修改后的字符串达到要求。于是他找到了你，希望你能帮助他解决问题，数据保证能在题目限制下形成回文字符串。

注:回文字符串：即一个字符串从前向后和从后向前是完全一致的字符串。例如字符串$abcba,aaaa,acca$都是回文字符串。字符串$abcd,acea$都不是回文字符串。

输入描述

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

保证字符串不会是空字符串。

字符串长度介于$[1,100000]$ 之间。

输出描述

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

样例$1$

输入

acca

输出

aaaa

说明： 原来的字符串已经是回文字符串了。但它不是题目条件下可以取得的字典序最小的回文字符串。将第二个字符和第三个字符都改为$a$可以获得字典序最小的回文字符串。

样例$2$

输入

abcde

输出

abcba

说明 将$de$改为$ba$可以获得字典序最小的回文字符串。