Longest Palindromic Substring Extraction

Alex is obsessed with palindromes. In this problem, you are given a string s consisting of lowercase letters. Your task is to extract the longest palindromic substring from s. A palindrome is a string that reads the same backward as forward. If there are multiple palindromic substrings of maximum length, you may output any one of them.

Note: The input string has a length between 1 and 1000. You should read the input from standard input (stdin) and write the answer to standard output (stdout).

For example:

Input: babad
Output: aba
Input: cbbd
Output: bb

</p>

inputFormat

The input consists of a single line, containing the string s (1 ≤ |s| ≤ 1000), which is composed only of lowercase letters.

outputFormat

Output the longest palindromic substring found in the input string. In case there are multiple answers, any valid one is acceptable.

## sample

babad

aba