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. In case there are multiple substrings of the same maximum length that are palindromic, return the first one that appears in the string.

For example, for s = "babad" the answer is "bab" because the first occurring longest palindrome is "bab" (although "aba" is also a valid answer, we require the first occurrence).

The solution should accept input via stdin and print the result to stdout.

Note: If the string is empty, simply output an empty string.

inputFormat

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

Input: A single line string.

outputFormat

Output the longest palindromic substring found in the input string. If the input is empty, output an empty string.

Output: A single line string representing the longest palindromic substring.

racecar

racecar