Longest Palindromic Substring

Given a string (s), find the longest palindromic substring in (s). A palindrome is a string that reads the same forward and backward. If there are multiple palindromic substrings of the same maximum length, output the one that appears first in (s). The input will be provided through standard input (stdin), and your program should print the result to standard output (stdout).

inputFormat

A single line containing the string (s). The string can be empty and its length does not exceed 1000 characters.

outputFormat

Print the longest palindromic substring of the input string. If multiple substrings of the same length are found, print the one that appears first.## sample

babad

bab