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. Solve the problem using efficient algorithms such as dynamic programming. The input is read from standard input (stdin) and the result should be printed to standard output (stdout).

inputFormat

A single line containing the string s.

outputFormat

Print the longest palindromic substring of s.## sample

babad

bab