说明

弗拉德找到了一个由若干个小写拉丁字母组成的字符串 s，他想把这个字符串变成一个回文字符串。

为此，他的想法是在这个字符串前方添加一个最短的字符串使s变成回文串。请帮帮他

弗拉德通过添加可以得到的最短的回文串是多少？

输入

输入一行包含一个字符串 s (0 <= s.length <= 5 * 10⁴)

输出

输出一行为组成的最短的回文字符串

样例

abccbadd

ddabccbadd

abc

cbabc

Limitation

1s, 1024KB for each test case.