说明

给定一个仅由小写字母组成的字符串 s ，你可以添加一些字符（也可以不加），使其构成回文串。

请你输出在添加字符数最少的前提下，能够构成字典序最小的回文串。

输入格式

输入共一行，一个字符串 s

输出格式

输出共一行，题目所求的回文串。

样例

ai

aia

提示

样例说明：字符串ai至少添加一个字符构成回文，该前提下，可以构造成aia、iai，但aia的字典序更小

数据范围：