Longest Palindromic Substring

Given a string s of length n, find and output its longest palindromic substring. A palindrome is a string that reads the same backward as forward. If there are multiple answers, output the one which appears first in the string.

For example, if s = "babad", both "bab" and "aba" are acceptable answers. In our expected implementation, the algorithm should return the one found first using the center expansion method.

The solution should implement an algorithm that runs in O(n²) time using the expand around center technique. The formula for the center expansion of a palindrome can be written in LaTeX as:

$$\text{while } left \ge 0 \text{ and } right < n \text{ and } s[left] = s[right]$$

Your program must read input from stdin and write the result to stdout.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output the longest palindromic substring found in the input string s.

babad

aba