Longest Palindromic Substring

Given a string (s), find the longest substring of (s) that is a palindrome. A palindrome is a string that reads the same forwards and backwards. For example, if (s = \texttt{abacdfgdcaba}), a possible correct answer is (\texttt{aba}) (since both 'aba' and 'aca' are correct, your program only needs to output one valid answer). Please note that the input will be given as a single line from standard input, and you should output the result to standard output.

inputFormat

The input consists of a single line containing a non-empty string (s). The string may contain lowercase and uppercase letters.

outputFormat

Output the longest palindromic substring found in (s) on a single line. If multiple answers exist, output any one of them.## sample

abacdfgdcaba

aba