Longest Palindromic Substring

Given a string \( s \), find its longest palindromic substring. A substring is palindromic if it reads the same forwards and backwards. If there are multiple substrings with the maximum length, return the one that appears first in \( s \).

Note: If the input string is empty, output an empty string.

inputFormat

The input is provided via standard input and consists of a single line representing the string \( s \).

outputFormat

Output via standard output the longest palindromic substring of \( s \). In case of multiple answers, output the first occurring substring.

babad

bab