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.