Longest Palindromic Substring Finder

Given a string s, your task is to find the longest palindromic substring in s as well as its starting index.

A palindrome is a string that reads the same forward and backward. For example, in the string "babad", both "bab" and "aba" are palindromic substrings, but you should return the one found using the specified approach.

The solution should read the input from standard input stdin and print the result to standard output stdout in the following format:

palindrome starting_index

Note: If multiple answers exist, return the one discovered first by the algorithm described in the sample solution.

Mathematically, if we denote the input string as $s$, you must output a palindrome $P$ and an integer $i$, where $P = s[i:i+\ell]$ and $\ell$ is the maximum length such that $P$ is a palindrome.

inputFormat

The input consists of a single line containing a non-empty string s.

outputFormat

Output the longest palindromic substring and its starting index separated by a space.

babad

bab 0