最长回文子串

题目描述

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

如果最长回文子串有多个，本题规定输出起始位置最靠前的那个。

回文串是指正着读和反着读都相同的字符串。

输入格式

输入一行，包含一个字符串 s。

输出格式

输出一行，表示 s 的最长回文子串。

数据范围

1 <= |s| <= 1000

字符串 s 仅由数字和英文字母组成。

样例 1

输入

babad

输出

bab

样例 2

输入

cbbd

输出

bb