Longest Palindromic Substring

Given a string s consisting of lowercase alphabetic characters, your task is to find the longest palindromic substring in s. A palindromic substring is a substring which reads the same forward as backward.

If there are multiple answers with the same maximum length, return the one that appears first in the string.

The solution should read input from standard input (stdin) and write output to standard output (stdout).

Note: A substring is a contiguous sequence of characters within the string.

inputFormat

The input consists of a single line containing a non-empty string s (with only lowercase letters).

outputFormat

Output the longest palindromic substring found within the string. If there are multiple palindromic substrings of maximum length, output the one that appears earliest in the string.

babad

bab