Find Palindromic Substrings

Given a string s, your task is to find all palindromic substrings in s and return a list of pairs (i, j) representing the starting and ending indices (inclusive) of each palindrome. A palindrome is a string that reads the same forwards and backwards. Note that every single character is considered a palindrome.

The resulting list must be sorted in increasing order first by the starting index and then by the ending index. Mathematically, if we denote the result as \(R\), then \[ R = sorted(R) \]

You should read the input from standard input (stdin) and output the result to standard output (stdout) in the Python list format, e.g., [(0, 0), (0, 2), ...].

inputFormat

The input consists of a single line containing the string s.

outputFormat

Output the list of pairs representing the starting and ending indices of each palindromic substring in the specified format.

ababa

[(0, 0), (0, 2), (0, 4), (1, 1), (1, 3), (2, 2), (2, 4), (3, 3), (4, 4)]