The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

constructive algorithms

data structures

greedy

hashing

strings

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Tricky and Clever Password

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn his very young years the hero of our story, king Copa, decided that his private data was hidden not enough securely, what is unacceptable for the king. That's why he invented tricky and clever password (later he learned that his password is a palindrome of odd length), and coded all his data using it.

Copa is afraid to forget his password, so he decided to write it on a piece of paper. He is aware that it is insecure to keep password in such way, so he decided to cipher it the following way: he cut *x* characters from the start of his password and from the end of it (*x* can be 0, and 2*x* is strictly less than the password length). He obtained 3 parts of the password. Let's call it *prefix*, *middle* and *suffix* correspondingly, both *prefix* and *suffix* having equal length and *middle* always having odd length. From these parts he made a string *A* + *prefix* + *B* + *middle* + *C* + *suffix*, where *A*, *B* and *C* are some (possibly empty) strings invented by Copa, and « + » means concatenation.

Many years have passed, and just yesterday the king Copa found the piece of paper where his ciphered password was written. The password, as well as the strings *A*, *B* and *C*, was completely forgotten by Copa, so he asks you to find a password of maximum possible length, which could be invented, ciphered and written by Copa.

Input

The input contains single string of small Latin letters with length from 1 to 10^{5} characters.

Output

The first line should contain integer *k* — amount of nonempty parts of the password in your answer (). In each of the following *k* lines output two integers *x*_{i} and *l*_{i} — start and length of the corresponding part of the password. Output pairs in order of increasing *x*_{i}. Separate the numbers in pairs by a single space.

Starting position *x*_{i} should be an integer from 1 to the length of the input string. All *l*_{i} must be positive, because you should output only non-empty parts. The middle part must have odd length.

If there are several solutions, output any. Note that your goal is to maximize the sum of *l*_{i}, but not to maximize *k*.

Examples

Input

abacaba

Output

1

1 7

Input

axbya

Output

3

1 1

2 1

5 1

Input

xabyczba

Output

3

2 2

4 1

7 2

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/01/2023 19:25:46 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|