Convert the String into a Palindrome
Given a string
s, you are allowed to add characters at the beginning of the string. Your task is to turn s into a palindrome while performing as few operations as possible.Input
The only line of the input contains a string
s (1 ≤ |s| ≤ 100 000).Output
The program should print the resulting palindrome string.
Examples
Input | Output |
abcd | dcbabcd |
aabc | cbaabc |
kayak | kayak |
epaper | repaper |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB