题目描述

回文串是指正读和反读都相同的字符串。例如，"aba"、"abba"、"a" 都是回文串，而 "abc"、"ab" 不是。

给定一个字符串 $s$，请找出其中最长的回文子串，并输出该子串。

你可以假定只有一个满足条件的最长回文串。

输入格式

输入一行字符串 $s$（$1 \le |s| \le 1000$）。字符串仅包含小写字母。

输出格式

输出最长回文子串。

样例 #1

样例输入 #1

abcdzdcab

样例输出 #1

cdzdc

样例 #2

样例输入 #2

aba

样例输出 #2

aba

样例 #3

样例输入 #3

cbbd

样例输出 #3

bb

样例 #4

样例输入 #4

a

样例输出 #4

a

提示

样例解释：

样例1：字符串 "abcdzdcab" 中，最长回文子串为 "cdzdc"，长度为 $5$。

样例2：字符串 "aba" 本身就是回文串，最长回文子串就是 "aba"。

样例3：字符串 "cbbd" 中，回文子串有 "c"、"b"、"b"、"d"、"bb"，其中最长的是 "bb"。

数据范围：

• 对于 $30\%$ 的数据：$1 \le |s| \le 20$
• 对于 $60\%$ 的数据：$1 \le |s| \le 200$
• 对于 $100\%$ 的数据：$1 \le |s| \le 1000$