Longest Palindromic Substring

Given a string s, find the longest palindromic substring within s. A substring is a contiguous sequence of characters in the string. If there are multiple palindromic substrings with the same maximum length, return the one that appears first in s.

A palindrome is a string that reads the same forwards and backwards. Formally, a string s of length n is a palindrome if $$ s[i] = s[n-i-1] \quad \text{for all} \quad 0 \le i < n. $$

Your task is to process the input string and output its longest palindromic substring.

inputFormat

The input consists of a single line containing the string s. The string will consist of printable ASCII characters.

outputFormat

Output a single line containing the longest palindromic substring of the input string. If there are multiple answers, output the one that appears first in the string.

banana

anana