Longest Palindromic Substring

The Mereside puzzle desk runs a column on words that read the same backwards as forwards -- level, noon, racecar. Readers post in long unbroken strings of letters and ask what is hiding inside them, so the desk needs the longest run of neighbouring characters anywhere in a submission that reads identically in both directions. A single character always qualifies, so there is always something to print. Sometimes two different runs tie on length, and the column's house rule is to print whichever of them starts nearer the front.

Task: Print the longest run of neighbouring characters that reads the same in both directions; if two runs tie on length, print the one that starts earliest.

Input

A single line holding 1 to 1000 characters, with no spaces. Characters may be upper or lower case, and case is part of the character: A and a do not match each other.

Output

One line holding that run and nothing else.

Example:

Input:
babad

Output:
bab