Longest Palindromic Substring

Given a string \(S\) consisting of lowercase alphabetic characters (and possibly spaces), find the longest palindromic substring contained in \(S\). A palindrome is a string that reads the same backward as forward. If there are multiple palindromic substrings of the same maximum length, return the one that appears first in \(S\).

For example, if \(S = \texttt{forgeeksskeegfor}\), the longest palindromic substring is \(\texttt{geeksskeeg}\).

inputFormat

The input is given in stdin and consists of a single line containing the string \(S\). The string may contain lowercase letters and spaces.

outputFormat

Output the longest palindromic substring found in the input string \(S\) to stdout. In case there are multiple answers, output the one that appears first.

babad

bab