Longest Palindromic Substring

Given a string s, find the longest palindromic substring in it. A palindrome is a sequence that reads the same backwards as forwards. If there are multiple palindromic substrings with the maximum length, return the one that appears first in the string.

For instance, for the input babad, the correct output is bab because it appears before aba in the original string.

The algorithm you implement should be efficient enough to handle strings of length up to 1000.

Recall that a palindrome must satisfy the condition \( s[i] = s[j] \) for its respective characters, and you may use the center expansion technique to solve this problem.

inputFormat

The input consists of a single line containing a string s. The string can include letters, spaces, and other printable characters, and its length is between 0 and 1000.

outputFormat

Output the longest palindromic substring in the input string s.

## sample

babad

bab

</p>