Longest Palindromic Substring

Given a string s, find the longest substring which is a palindrome.

A palindrome is a string that reads the same forwards and backwards, e.g., it satisfies the condition $$s = s^R$$, where $$s^R$$ denotes the reverse of s. If there are multiple answers, output the first one found by the algorithm.

inputFormat

The input consists of a single line which contains the string s. The string will consist of visible ASCII characters only.

outputFormat

Output the longest palindromic substring of the given string. If there are multiple valid answers, output the one found first.## sample

babad

bab