A word is the nonempty sequence of symbols a1a2…an. A palindrome is the word a1a2…an that is read from the left to the right and from the right to the left the same way (a1a2…an = anan−1…a1). If
S1 = a1a2…an and
S2 = b1b2…bm, then S1S2 =
a1a2…anb1b2…bm. The input contains some word S1. You are to find a nonempty word S2 of the minimal length that S1S2 is a palindrome.
The first input line contains S1 (it may consist only of the Latin letters). It’s guaranteed that the length of S1 doesn’t exceed 10000 symbols.
Problem Author: Denis Nazarov
Problem Source: USU Junior Championship March'2005