Longest Palindromic Substring

Given a string s, your task is to find the longest palindromic substring in s. A palindrome is a string that reads the same backwards as forwards. If there are multiple palindromic substrings of the same maximum length, you may return any one of them.

The solution should use standard input and output. In particular, the input will be a single line containing the string, and you must print the longest palindromic substring to standard output.

Hint: You can use the expand around center technique to check for palindromes. Mathematically, a string s is a palindrome if for indices \( i \) and \( j \) such that \( 0 \leq i, j < |s| \), the following holds:

[ s[i] = s[|s| - i - 1] ]

inputFormat

Input is provided via standard input (stdin) as a single line containing the string s. The string consists of only printable characters.

outputFormat

Output the longest palindromic substring found in the input string via standard output (stdout).

babad

aba