题目描述

阿卡有一个只包含小写字母的字符串 $s$。

你需要在这个字符串中加入最少的字符后重排，使得这个字符串回文。

你需要输出你加入字符后重排后的字符串。

注意，要求加入的字符数量最少。

输入格式

一行一个只包含小写字母的字符串。

输出格式

一行一个只包含小写字母的字符串表示你的答案。

样例 #1

样例输入 #1

aba

样例输出 #1

aba

样例 #2

样例输入 #2

aaa

样例输出 #2

aaa

样例 #3

样例输入 #3

qwq

样例输出 #3

qwq

样例 #4

样例输入 #4

qwqwq

样例输出 #4

qwqwq

样例 #5

样例输入 #5

awa

样例输出 #5

awa

样例 #6

样例输入 #6

awawa

样例输出 #6

awawa

样例 #7

样例输入 #7

bob

样例输出 #7

bob

样例 #8

样例输入 #8

a

样例输出 #8

a

样例 #9

样例输入 #9

cyx

样例输出 #9

xycyx

样例 #10

样例输入 #10

gmx

样例输出 #10

gmxmg

样例 #11

样例输入 #11

alice

样例输出 #11

alicecila

样例 #12

样例输入 #12

incra

样例输出 #12

incrarcni

样例 #13

样例输入 #13

aab

样例输出 #13

aba

样例 #14

样例输入 #14

cat

样例输出 #14

catac

样例 #15

样例输入 #15

dog

样例输出 #15

dogod

提示

【样例解释 #1 至 #8】

字符串本身就已经回文了，因此不用进行任何操作。

【数据范围】

设 $|S|$ 为字符串 $S$ 的长度。

对于 $90\%$ 的数据，保证 $|S| = 1$。

对于另外 $2\%$ 的数据，保证 $|S| \le 4$。

对于另外 $2\%$ 的数据，保证 $|S| \le 500$。

对于另外 $2\%$ 的数据，保证 $|S| \le 2000$。

对于另外 $2\%$ 的数据，保证 $|S| \le 10^5$。

对于另外 $2\%$ 的数据，保证 $|S| \le 10^7$。

保证 $|S|$ 的奇偶性所占不同类型的数据数量相同。