ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Championship March'2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Palindrome. Again Palindrome

Time limit: 1.0 second
Memory limit: 64 MB
A word is the nonempty sequence of symbols a1a2an. A palindrome is the word a1a2an that is read from the left to the right and from the right to the left the same way (a1a2an = anan−1a1). If S1 = a1a2an and S2 = b1b2bm, then S1S2 = a1a2anb1b2bm. The input contains some word S1. You are to find a nonempty word S2 of the minimal length that S1S2 is a palindrome.

Input

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.

Output

S1S2.

Samples

inputoutput
No
NoN
OnLine
OnLineniLnO
AbabaAab
AbabaAababA
Problem Author: Denis Nazarov
Problem Source: USU Junior Championship March'2005
To submit the solution for this problem go to the Problem set: 1354. Palindrome. Again Palindrome