Home Web Board ProblemSet Standing Status Statistics
1.该OJ由于交换空间受限,暂不不支持万能头文件:bits/stdc++.h!!! 2.该OJ如果是长整型的话,C的输入输出请使用%lld!!!
Problem G: Prefixes and Suffixes

Problem G: Prefixes and Suffixes

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 11  Solved: 4
[Submit][Status][Web Board]

Description

  Once a man is bent, someone else will ride on your back, and what you do should be straight forward.Although you go slowly, you never go back.Never underestimate your power.Get to the point. 

  You have a string s,where len is the length of string s, and si its i-th character.The prefix is s[0..i]  (0 ≤ i < len). The suffix is s[i..len-1] (0 ≤ i < len).

  Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.( Including the original string s.)

Input

The single line contains a string s (1 ≤ len≤ 105) — . The string only consists of uppercase English letters.

Output

In the first line, print integer k (0 ≤ k ≤ len) — the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers ai bi. Numbers ai bi mean that the prefix of the length ai matches the suffix of length ai and occurs in string s as a substring bi times. Print pairs li bi in the order of increasing ai.

Sample Input

ABACABA
AAA

Sample Output

3
1 4
3 2
7 1
3
1 3
2 2
3 1

HINT

[Submit][Status][Web Board]