Longest Palindromic Substring

Given a string s, find the longest palindromic substring contained in s. A palindrome is a sequence of characters that reads the same backward as forward. If there exist multiple answers, any one of the longest palindromic substrings is accepted.

For example, if s = "babad", both "bab" and "aba" are valid answers.

The solution should handle strings containing letters, digits, special characters, and even spaces.

inputFormat

The input consists of a single line containing the string s. The string may contain any printable characters.

outputFormat

Output the longest palindromic substring of the given string s.## sample

a

a