403666: GYM101237 C The Palindrome Extraction

Do you like palindromes as much as we do? Then this problem and the next one are dedicated to you.

As you know, a palindrome is a string S that is equal to the reverse of itself: .

You are given a string S. Your task is to find five strings, A, B, C, D and E, such that the following conditions are satisfied:

1. S = A + B + C + D + E, where  +  denotes string concatenation (each of the strings A, B, C, D and E can be empty).
2. B + D is a palindrome.
3. |B + D| is maximal possible, where |X| denotes the length of string X.

One of our team members says that his grandma would solve this problem in less then a minute. What about you?

The input contains the string S (1 ≤ |S| ≤ 100 000). The string consists of lowercase English letters.

On the first line of output, print the maximal possible value of |B + D|.

On the second and the third lines, print two numbers denoting 1-indexed positions of the first and the last characters of substrings B and D in string S. If one of the substrings is empty, output "-1 -1" for its positions.

If there are several possible answers, print any one of them.

abcdcxxxba

7
1 5
9 10