Find Longest Palindromic Substring

The string contains only uppercase English letters. Find the longest contiguous palindromic substring of length at least 2; if there are several longest results, output the lexicographically smallest string; if none exists, output None.

输入格式

One line containing a string of uppercase letters. The original gave no length bound; this site adds 1≤length≤1000.

输出格式

Output the chosen palindrome string or None.

样例 1

输入：

YABCCBAZ

输出：

ABCCBA

样例 2

输入：

ABC

输出：

None

样例 3

输入：

ZZXAA

输出：

AA

样例说明

The outputs of the three public examples are, in order: ABCCBA; None; AA. Verified by independent enumeration or direct simulation.