Longest Lexicographic Palindrome Substring

You are given a string \( s \) consisting of lowercase English letters. Your task is to find the longest substring of \( s \) that is a palindrome. In case there are multiple palindromic substrings with the maximum length, you should output the lexicographically smallest one.

A palindrome is a string that reads the same forwards and backwards. For example, \( \texttt{aba} \) and \( \texttt{racecar} \) are palindromic strings.

Note: Lexicographical order follows the standard dictionary order. For example, \( \texttt{aba} \) is lexicographically smaller than \( \texttt{aca} \).

inputFormat

The input is provided via standard input (stdin) as a single string ( s ) containing only lowercase English letters. There are no spaces in the string.

outputFormat

Output the longest palindromic substring which is also lexicographically smallest among those of maximum length to standard output (stdout).## sample

abacdfgdcaba

aba