Longest Palindromic Substring

Problem statement

A text editor highlights the longest contiguous substring that reads the same forwards and backwards. Find that substring without changing character order. If several longest palindromes exist, return the one with the smallest starting position in the input.

Input format

One line: a nonempty lowercase string s.

Output format

Print the longest palindromic substring, breaking ties by earliest starting position.

Constraints

1 <= length of s <= 2000; lowercase English letters only.

Sample input

babad

Sample output

bab