CF30E.Tricky and Clever Password

In 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.

在我们故事主人公——国王科帕年少时，他觉得自己的私人数据隐藏得不够安全，而这对于一位国王而言是不可接受的。因此，他发明了一种巧妙而精巧的密码（后来他才得知该密码是一个长度为奇数的回文串），并用它对所有数据进行了加密。

科帕担心自己会忘记密码，于是决定将密码写在一张纸上。他深知以这种方式保存密码并不安全，因此决定进一步对其进行加密：他从密码的开头和结尾各截取了 $x$ 个字符（$x$ 可以为 $0$，且 $2x$ 严格小于密码长度），从而得到密码的三部分。我们分别称其为 prefix（前缀）、middle（中间部分）和 suffix（后缀），其中 prefix 和 suffix 长度相等，而 middle 的长度恒为奇数。接着，他用这三部分构造了一个字符串：

$$A\,+\,\text{\textit{prefix}}\,+\,B\,+\,\text{\textit{middle}}\,+\,C\,+\,\text{\textit{suffix}},$$

其中 $A$、$B$ 和 $C$ 是科帕自行设计的某些（可能为空的）字符串，符号 « + » 表示字符串连接。

多年过去了，就在昨天，国王科帕找到了那张写有他加密后密码的纸片。然而，密码本身以及字符串 $A$、$B$ 和 $C$ 都已被科帕彻底遗忘。因此，他请求你找出一个可能的最大长度的密码，该密码有可能由科帕设计、加密并写在这张纸上的。

The input contains single string of small Latin letters with length from 1 to 105 characters.

输入包含一个由小写拉丁字母组成的字符串，长度为 1 到 $10^5$ 个字符。

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.

第一行应包含整数 $k$ —— 你答案中密码非空部分的数量（）。接下来的 $k$ 行中，每行输出两个整数 $x_i$ 和 $l_i$ —— 密码对应部分的起始位置与长度。请按 $x_i$ 递增的顺序输出这些数对。每对数之间用一个空格分隔。

起始位置 $x_i$ 应为介于 $1$ 到输入字符串长度之间的整数。所有 $l_i$ 必须为正整数，因为你只能输出非空部分。中间部分的长度必须为奇数。

若存在多个解，输出任意一个即可。注意：你的目标是最大化所有 $l_i$ 的总和，而非最大化 $k$。