Longest Palindromic Substring

Given a string, your task is to find its longest palindromic substring. A palindrome is a string that reads the same backwards as forwards. If there are multiple longest palindromic substrings, return the one that appears first based on the algorithm's logic. If the input string is empty, output an empty string.

For example, for the input babad, a correct output would be bab (note that aba is also a valid answer, but your implementation should be consistent in its output).

inputFormat

The input consists of a single line containing a string of at most 1000 characters.

outputFormat

Print the longest palindromic substring found in the input. If there are multiple with the same maximum length, print the one that your algorithm finds first. For an empty input string, output an empty string.## sample

babad

bab