Longest Palindromic Substring

Given a string s, your task is to determine the longest palindromic contiguous substring within s. A palindrome is a sequence of characters that reads the same forwards and backwards, i.e., $$s = reverse(s)$$. If there are multiple palindromic substrings of maximum length, return the one that appears first in s.

inputFormat

The input consists of a single line containing the string s. The string may include any characters.

outputFormat

Output the longest palindromic substring found in s.## sample

babad

bab