Longest Palindromic Substring

Return a palindromic contiguous substring of maximum length from the original string. If there are several longest answers, return any one of them; the lexicographically smallest or the earliest one must not be additionally required. A single character is also a palindrome.

输入格式

One line containing a string s of ASCII English letters or digits. The original bound 1≤|s|≤1000 is kept, and the string is case-sensitive.

输出格式

Output any one longest palindromic substring, optionally followed by one terminating newline; do not output quotes or explanatory text.

样例 1

输入：

babad

输出：

aba

样例 2

输入：

cbbd

输出：

bb

样例 3

输入：

7

输出：

7

样例说明

The outputs of the three public examples are, in order: aba; bb; 7. Verified by independent enumeration or direct simulation.