A palindrome string is a palindrome if it can be read the same forwards and backwards. The longest palindrome in a string is the longest substring which is palindrome.

Your task is to find the longest palindrome in the given string.

Input

The first and only line of the input contains a string with n characters.

Output

Output a single line with the longest palindrome in the given string.

Limits

• 1 \le n \le 10^6
• Each word consists of only English lower case letters a-z.

Example

Input:

aybabtu

Output:

bab