Longest Palindromic Substring

Given a string \( s \), find and return its longest palindromic substring. A palindrome is a string that reads the same forwards and backwards, and a substring is a contiguous block of characters.

Your task is to read a single string from stdin and output its longest palindromic substring to stdout. If multiple answers exist, output the one found by the algorithm.

inputFormat

The input consists of a single line containing the string \( s \). The string may be empty.

outputFormat

Output the longest palindromic substring of the input string.

babad

aba