Longest Palindromic Substring

Given a string s, find the longest palindromic substring within it. A palindrome is a string that reads the same forwards and backwards. If there are multiple palindromic substrings with the same maximum length, output the one that appears first in the string.

The problem can be formulated mathematically as finding indices \(i\) and \(j\) (with \(0 \le i \le j < n\), where \(n\) is the length of s) such that:

[ d(s[i \ldots j]) = s[i \ldots j] \quad \text{and} \quad (j - i + 1) \text{ is maximized.} ]

Input is provided via standard input, and output must be printed to standard output.

inputFormat

Input Format: A single line containing the string s.

Note: The string may contain only alphabetical characters. It can also be empty.

outputFormat

Output Format: Print the longest palindromic substring found in the string s.## sample

babad

bab