题目描述

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

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

输入格式

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

输出格式

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

ai

aia

样例解释 1

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

iai

iai

样例解释 2

不用添加任何字符

abca

abcba

数据范围

设 $|s|$ 为字符串 $s$ 的长度，则有：

• 对于 $30\%$ 的数据，$1\leq |s|\leq 10$
• 对于 $60\%$ 的数据，$1\leq |s|\leq 100$
• 对于 $100\%$ 的数据，$1\leq |s|\leq 10^3$