Longest Palindromic Substring

Given a string (s), find the longest palindromic substring in (s). A palindrome is a string that reads the same backward as forward. If there are multiple answers, return the one that appears first.

For example, when (s = \texttt{babad}), the answer is (\texttt{bab}) (note that (\texttt{aba}) is also a valid answer, but you must return the first occurrence based on your algorithm's discovery).

Constraints: (1 \leq |s| \leq 1000).

Your solution should read from standard input and output to standard output.

inputFormat

Input is provided via standard input (stdin) as a single line containing the string (s).

outputFormat

Output the longest palindromic substring found in (s) to standard output (stdout).## sample

babad

bab