Longest Palindromic Substring

Medium

Given a string, print its longest palindromic substring. Input format: - One line: s If multiple longest palindromic substrings exist, print the earliest one.

Constraints

1 <= s.length <= 10^5

Sample tests

Sample 1

Input

babad

Output

bab

Sample 2

Input

cbbd

Output

bb