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 forward and backward. For example, in the string "babad", both "bab" and "aba" are palindromic substrings; your solution should output one of them. In this problem, if there exist multiple answers, outputting the one found by the algorithm is acceptable.

The problem can be mathematically formulated as follows: Find indices \( i \) and \( j \) with \( 0 \leq i \leq j < n \) (where \( n \) is the length of the string) such that the substring \( s[i\ldots j] \) is a palindrome and its length \( (j-i+1) \) is maximized.

inputFormat

The input is given via standard input (stdin) and consists of a single line containing the string s.

Note: The string s will only contain printable characters and will not exceed 1000 characters in length.

outputFormat

The output should be printed to standard output (stdout) and consist of the longest palindromic substring found in s.

## sample

babad

aba

</p>