432_D. Prefixes and Suffixes
You have a string s = s1s2...s|s|, where |s| is the length of string s, and si its i-th character. 

Let's introduce several definitions:

  * A substring s[i..j] (1 ≤ i ≤ j ≤ |s|) of string s is string sisi + 1...sj. 
  * The prefix of string s of length l (1 ≤ l ≤ |s|) is string s[1..l]. 
  * The suffix of string s of length l (1 ≤ l ≤ |s|) is string s[|s| - l + 1..|s|]. 



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.

Input

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

Output

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

Examples

Input

ABACABA


Output

3
1 4
3 2
7 1


Input

AAA


Output

3
1 3
2 2
3 1
```python
def zeta(s):
	n = len(s)
	z = [0]*n
	l,r = 0,0
	for i in range(1,n):
		if(i<=r): z[i] = min(r-i+1,z[i-l])
		while(i+z[i]<n and s[z[i]]==s[i+z[i]]):
			z[i]+=1
		if(i+z[i]-1>r):
			l=i
			r = i+z[i]-1
	return z
s = input()
n = len(s)
z = zeta(s)
l = [0]*n
for i in z:
	l[i]+=1
cum = [l[-1]]
for i in range(n-2,-1,-1):
	cum.append(l[i]+cum[-1])
cum = cum[::-1]
ans = [(n,1)]
for i in range(n-1,0,-1):
	if(i+z[i]==n):
		ans.append((n-i,cum[n-i]+1))

print(len(ans))
for i in sorted(ans):
	print(*i)

	 		 		 		  	 		     	 	    	
```