如果一个字符串从左到右和从右到左读取相同,则称为回文。例如,“kazak”、“oo”、“r”和“mikhailrubinchikkihcniburliahkim”是回文,但字符串“abb”和“ij”不是。
给定一个由小写拉丁字母组成的字符串 s。您可以立即选择字符串中的任何位置并将该位置的字母更改为任何其他小写字母。因此每次更改后字符串的长度都不会改变。首先你可以改变s中的一些字母。然后您可以根据需要排列字母的顺序。排列不算作更改。
您应该获得具有最少变化次数的回文。如果有多种方法可以做到这一点,您应该获得按字典顺序(按字母顺序)最小的回文。因此,首先应该最小化更改的数量,然后按字典顺序最小化回文。
输入
唯一一行包含仅由小写拉丁字母组成的字符串 s (1 ≤ |s| ≤ 2·105)。
输出
打印可以通过最少的更改次数获得的字典顺序最小的回文。
示例
输入 #1
aabc
输出 #1
abba
输入 #2
aabcd
输出 #2
abcba