Description

输入一个只包含大小写字母的字符串S,你可以进行若干次操作：

选择字符串中任意一个字母修改成任意字母

请你使用尽可能少的操作次数，使得 S 变成一个回文串

回文串定义是正着读和反着读相同

多解时输出字典序(按ASCII码排序)最小的情况

Format

Input

一个只包含大小写字母的字符串S，$|S|\le10^5$

Output

输出你修改的字符串

Samples

abba

abba

Limitation

1s, 1024KiB for each test case.