Longest Double Palindromic Substring

A palindrome is a string that reads the same forward and backward. For example, acbca is a palindrome while abc is not, since the reverse of abc is cba which is different.

Given a string $S$ of length $n$, find its longest substring $T$ which is a double palindrome. This means that $T$ can be split into two non-empty parts $X$ and $Y$ (i.e. $|X|,|Y|\ge1$) such that both $X$ and $Y$ are palindromes.

inputFormat

The input consists of a single line containing the string $S$.

Format: A string $S$ with length $n$.

outputFormat

Output the longest double palindromic substring $T$ of $S$. If multiple answers exist, output any one of them.

Format: A string representing the answer.

sample

abaaba

abaaba