403666: GYM101237 C The Palindrome Extraction

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. The Palindrome Extractiontime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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

Output

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.

ExamplesInput
abcdcxxxba
Output
7
1 5
9 10

加入题单

上一题 下一题 算法标签: