Longest Palindromic Substring

You are given a string s. Your task is to find and return the longest palindromic substring contained within s. If there are multiple substrings with the same maximum length, return the one that appears first in the string.

The palindromic substring is defined as a sequence of characters which reads the same backwards as forwards. For example, in the string "babad", the answer can be either "bab" or "aba". However, using the typical center expansion method, the first occurring result (in our implementation) will be returned.

Formally, if you denote the input string by ( s ), you need to find a substring ( s[i \ldots j] ) such that it is a palindrome (i.e. ( s[i \ldots j] = s[j \ldots i] )) and its length is maximized.

inputFormat

The input consists of a single line containing the string s where 1 \leq |s| \leq 1000.

outputFormat

Output the longest palindromic substring found in s on a single line.## sample

a

a