Longest Palindromic Substring

Your task is to design an algorithm that finds the longest palindromic substring within a given string.

A palindrome is a sequence of characters that reads the same forwards and backwards. Formally, a string \( s \) is a palindrome if \( s = s^{R} \), where \( s^{R} \) denotes the reverse of \( s \).

If multiple palindromic substrings of maximum length exist, you may output any one of them.

inputFormat

The input consists of a single line containing a string composed solely of lowercase English letters. The length of the string satisfies \(1 \leq |s| \leq 1000\).

Input is provided via standard input (stdin).

outputFormat

Output a single line containing the longest palindromic substring found in the input string. If there are multiple correct answers, output any one of them.

Output should be sent to standard output (stdout).

babad

bab