Longest Palindromic Substring

Given a string s, your task is to find the longest palindromic substring in s. A palindrome is a string that reads the same backward as forward. If there are multiple answers, any one of them is accepted. If the input string is empty, output an empty string.

Constraints: $$1 \leq |s| \leq 10^3$$ and s contains only printable ASCII characters.

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output the longest palindromic substring in s. If there are multiple substrings of maximum length, output any one of them. In the case that the string is empty, output an empty string.

babad

bab