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

To check your solution you need to sign in
Sign in to continue