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. For example, for the input string babad, the longest palindromic substring can be bab (or aba, however, your solution should output the first longest palindrome found by expanding around centers). The input string may contain any characters and can be empty. Your solution should read from standard input and write the result to standard output.

inputFormat

The input consists of a single line containing the string ( s ) for which you need to find the longest palindromic substring.

outputFormat

Output the longest palindromic substring found in the input string ( s ) to standard output.## sample

babad

bab