You have a string s = s_1s_2...s_{|}s|, where |s| is the length of string s, and s_{i} its i-th character. 

Let's introduce several definitions:  A substring s[i..j] (1 ≤ i ≤ j ≤ |s|) of string s is string s_{i}s_{i} + 1...s_{j}.  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 s_1s_2...s_{|}s| (1 ≤ |s| ≤ 10^5) — 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 l_{i} c_{i}. Numbers l_{i} c_{i} mean that the prefix of the length l_{i} matches the suffix of length l_{i} and occurs in string s as a substring c_{i} times. Print pairs l_{i} c_{i} in the order of increasing l_{i}.


-----Examples-----
Input
ABACABA

Output
3
1 4
3 2
7 1

Input
AAA

Output
3
1 3
2 2
3 1

Difficulty: interview

Starter code:

Solutions:
s = input()
n = len(s)
p = [0] * n
k = 0
for i in range(1, n):
  while k != 0 and s[k] != s[i]:
    k = p[k - 1]
  if s[k] == s[i]:
    k += 1
  p[i] = k
a = []
k = n
while k != 0:
  a += [k]
  k = p[k - 1]
c = [0] * (n + 1)
for i in range(n):
  c[p[i]] += 1
for i in range(n - 1, 1, -1):
  c[p[i - 1]] += c[i]
print(len(a))
for t in reversed(a):
  print(t, c[t] + 1)

s = ' ' + input()
n = len(s)
r, c = [-1] * n, [1] * n
for i in range(1, n):
    r[i] = r[i - 1] + 1
    while r[i] and s[r[i]]  != s[i]:
        r[i] = r[r[i] - 1] + 1
d, n = [], n - 1
for i in range(n, 1, -1): c[r[i]] += c[i]
while n > 0:
  d.append(str(n) + ' ' + str(c[n]))
  n = r[n]
print(len(d))
d.reverse()
print('\n'.join(d))

s=input()
n=len(s)
p=[0]
for i in range(1,n):
    j=p[i-1]
    while j>0 and s[j]!=s[i]:
        j=p[j-1]
    if s[j]==s[i]:
        j+=1
    p.append(j)
a = []
k = n
while k != 0:
    a += [k]
    k = p[k - 1]
c = [0] * (n + 1)
for i in range(n):
    c[p[i]] += 1
for i in range(n - 1, 1, -1):
    c[p[i - 1]] += c[i]
print(len(a))
for t in a[::-1]:
    print(t, c[t] + 1)

def Count(s, t):
    res = 0
    for i in range(len(s) - len(t) + 1):
        if s[i:i+len(t)] == t:
            res += 1
    return res
s = input()
n = len(s)
p = [0] * n
z = [0] * n
ans = [0] * n 
#Prefix 
for i in range(1, n):
    p[i] = p[i - 1]
    while p[i] > 0 and s[i] != s[p[i]]:
        p[i] = p[p[i] - 1]
            
    if s[i] == s[p[i]]:
        p[i] += 1
#Z func
l = r = 0
for i in range(1, n):
    if i <= r:
        z[i] = min(z[i - l], r - i + 1)
    while i + z[i] < n and s[i + z[i]] == s[z[i]]: z[i] += 1
    
    if i + z[i] - 1 > r:
        l, r = i, i + z[i] - 1


#for i in range(n - 2, -1, -1):
#    ans[i] += ans[i + 1] + count[i + 1]

for i in range(n):
    if z[i] > 0:
        ans[z[i] - 1] += 1
for i in range(n - 2, -1, -1):
    ans[i] += ans[i + 1] 
output = []
for i in range(n):
    if z[n - i - 1] == i + 1:
        output.append((i, ans[i]))
print(len(output) + 1)
for i in range(len(output)):
    print(output[i][0] + 1, output[i][1] + 1)
print(n, 1)


def Count(s, t):
    res = 0
    for i in range(len(s) - len(t) + 1):
        if s[i:i+len(t)] == t:
            res += 1
    return res

s = input()
n = len(s)
p = [0] * (n + 1)
z = [0] * n
ans = [0] * (n + 1)
#Prefix 
for i in range(1, n):
    p[i] = p[i - 1]
    while p[i] > 0 and s[i] != s[p[i]]:
        p[i] = p[p[i] - 1]
            
    if s[i] == s[p[i]]:
        p[i] += 1
#Z func
l = r = 0
for i in range(1, n):
    if i <= r:
        z[i] = min(z[i - l], r - i + 1)
    while i + z[i] < n and s[i + z[i]] == s[z[i]]: z[i] += 1
    
    if i + z[i] - 1 > r:
        l, r = i, i + z[i] - 1


#for i in range(n - 2, -1, -1):
#    ans[i] += ans[i + 1] + count[i + 1]

for i in range(n):
    ans[p[i]] += 1
#print(ans)
for i in range(n - 1, 0, -1):
    ans[p[i - 1]] += ans[i]
   # print(i, ': ', ans) 
output = []
for i in range(n):
    if z[n - i - 1] == i + 1:
        output.append((i, ans[i + 1]))
print(len(output) + 1)
for i in range(len(output)):
    print(output[i][0] + 1, output[i][1] + 1)
print(n, 1)


from itertools import accumulate

def z_algorithm(s):
    n = len(s)
    l, d = 1, 0
    ans = [0] * n
    ans[0] = n
    while l < n:
        while l + d < n and s[d] == s[l + d]:
            d += 1
        ans[l] = d
        if d == 0:
            l += 1
            continue
        k = 1
        while l + k < n and k + ans[k] < d:
            ans[l + k] = ans[k]
            k += 1
        l += k
        d -= k
    return ans

z = z_algorithm(input())
n = len(z)
ct = [0] * (n + 1)
match = [False] * (n + 1)
for i, v in enumerate(z):
    ct[v] += 1
    match[n - i] = (n - i) == v
for i in range(n - 1, -1, -1):
    ct[i] += ct[i + 1]
buf = []
for i, v in enumerate(ct):
    if i > 0 and v > 0 and match[i]:
        buf.append('{} {}'.format(i, v))
print(len(buf))
print('\n'.join(buf))


s = str(input())

lps = [0]*100005
dp = [0]*100005
ada = [0]*100005
tunda = [0]*100005

n = len(s)

i = 1
j = 0
lps[0] = 0

while(i < n):
    if (s[i] == s[j]):
        j += 1
        lps[i] = j
        i += 1
    elif (j == 0):
        lps[i] = 0
        i += 1
    else:
        j = lps[j-1]


for i in range(n-1,-1,-1):
    tunda[i] += 1
    dp[lps[i]] += tunda[i]
    if (lps[i]):tunda[lps[i]-1] += tunda[i]

j = n

"""
for i in range(n):
    print("SAD", i, lps[i])
"""

vector = []

while(1):
    vector.append((j,1+dp[j]))
    j = lps[j-1]
    if (j == 0): break


vector.reverse()

print(len(vector))
for i in vector:
    print(i[0], i[1])


def prefixFunction(s):
	j=0
	p=[0 for x in s]
	for i in range(1,len(s)):
		while j>0 and s[j]!=s[i]:
			j=p[j-1]
		if (s[j]==s[i]):j+=1
		p[i]=j
	return p
s=input()
p=prefixFunction(s)
n=len(s)
freq=[0 for i in range(n)]

for i in range(n):
    freq[p[i]]+=1

for i in range(n-1,0,-1):
    freq[p[i-1]]+=freq[i]

pos =n-1
ans=[[n,1]]
while pos>0:
        if p[pos]>1:
                ans.append([p[pos],freq[p[pos]]+1])
        pos=p[pos]-1

if len(s)>1 : 
        f= s.count(s[0])
        if s[0] == s[len(s)-1] : ans.append([1,f])
print(len(ans))
for i in sorted (ans):
    print(i[0],i[1])

    


s=input()
n=len(s)
if n==1:
    print('1\n1 1\n')
    return
p=[-1]*n
q=-1
for i in range(1,n):
    while q>=0 and s[i]!=s[q+1]:
        q=p[q]
    if s[i] == s[q + 1]:
        q+=1
        p[i]=q
#print(p)
c=[1]*n
for i in range(n-1,-1,-1):
    if p[i]>=0:
        c[p[i]]+=c[i]
#print(c)
ans=[(n,1)]
q=p[n-1]
while q>=0:
    ans.append((q+1,c[q]))
    q=p[q]
print(len(ans))
print('\n'.join([' '.join(map(str,x)) for x in reversed(ans)]))


dep = dict()

def kmp(st):
    tam = len(st)
    pi = [0]*tam
    for i in range(1,tam):
        j = pi[i-1]
        while j > 0 and st[j] != st[i]:
            j = pi[j-1]
        if st[j] == st[i]:
            pi[i] = j + 1
        dep[pi[i]] = pi[pi[i]-1]
    return pi


s = input()
arr = kmp(s)
points = [0] * len(s)
toimp = list()
actpi = arr[-1]
while actpi != 0:
    toimp.append(actpi)
    actpi = arr[actpi-1]

toimp.sort()
for i in range(len(arr)):
    points[arr[i]] += 1

for i in range(len(s)-1,0, -1):
    if i in dep:
        points[dep[i]] += points[i]

print(len(toimp)+1)
for i in toimp:
    print(str(i) + " " + str(points[i]+1))
print(str(len(s)) + " 1")


import heapq
from bisect import bisect_left, bisect_right, insort
from collections import Counter
from collections import OrderedDict
from collections import deque
from itertools import accumulate, product

import math

R = lambda: map(int, input().split())
s = input()
l, r, z = 0, 0, [0] * len(s)
for i in range(1, len(s)):
    if i > r - 1:
        l = r = i
        while r < len(s) and s[r] == s[r - i]:
            r += 1
        z[i] = r - l
    elif z[i - l] < r - i:
        z[i] = z[i - l]
    else:
        l = i
        while r < len(s) and s[r] == s[r - i]:
            r += 1
        z[i] = r - l
sz = sorted(z[:])
res = []
for i in range(len(s) - 1, 0, -1):
    if z[i] == len(s) - i:
        res.append((z[i], len(sz) - bisect_left(sz, z[i])))
print(len(res) + 1)
for x in res:
    print(x[0], x[1] + 1)
print(len(s), 1)


def z_advanced(s):
    """An advanced computation of Z-values of a string."""

    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n + k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k + n - 1
        else:
            # If k is inside the current Z-box, consider two cases.

            p = k - lt  # Pair index.
            right_part_len = rt - k + 1

            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
    return Z

def kmptab(s):
    tab = [0]*len(s)
    i = 1
    j = 0
    while i < len(s):
        if s[i] == s[j]:
            tab[i] = j + 1
            i += 1
            j += 1
        else:
            if j != 0:
                j = tab[j-1]
            else:
                i += 1
    return tab

def __starting_point():
    s = input()
    tab = kmptab(s)
    my_set = set()
    i = len(s)
    while i != 0:
        my_set.add(i)
        i = tab[i-1]
    V = []
    dict = {}
    for i in my_set:
        V.append(i)
        dict[i] = 0
    Z = z_advanced(s)

    v = []
    V.sort()
    my_tab = [0]*(len(s)+1)
    # print(Z)
    for i in Z:
        my_tab[i] += 1
    somme = 0
    # print(my_tab)
    for i in range(len(my_tab)-1, -1, -1):

        my_tab[i] += somme
        somme = my_tab[i]
    # print(my_tab)
    for i in dict:
        dict[i] = my_tab[i]
        v.append((dict[i], i))
    v.sort(key=lambda tup: tup[1])
    print(len(v))
    for i in v:
        print(str(i[1]) + " " + str(i[0]))

__starting_point()

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)



#!/usr/bin/env python3
"""Compute z function."""


def compute_z(data):
    z = [0 for _ in range(len(data))]
    z[0] = len(data)
    l = 0
    r = 0
    for i in range(1, len(data)):
        if i <= r: # nu am explorat
            z[i] = min(z[i-l], r-i+1)
        while i + z[i] < len(data) and data[z[i]] == data[i+z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            r = i + z[i] - 1
            l = i
    return z


data = input() # input -> eval 2.x ; input = read 
# print(data)
n = len(data)
z = compute_z(data)
feq_z = [0 for _ in range(n)]  # range(3) = 0, 1, 2
for value in z:
    if value == 0:
        continue
    index = value - 1
    feq_z[index] += 1


for i in range(n-2, -1, -1):
    feq_z[i] += feq_z[i+1]

# print(z)
# print(feq_z)
count = 0 
for i in range(n-1, -1, -1):
    if z[i] == n - i:
        count += 1
print(count)
for i in range(n-1, -1, -1):
    if z[i] == n - i:
        print("{} {}".format(z[i], feq_z[z[i]-1]))


def zfunc(s):
    n = len(s)
    z = [0] * n
    left = right = 0
    for i in range(1, n):
        if i <= right:
            z[i] = min(z[i - left], right - i + 1)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > right:
            left, right = i, i + z[i] - 1
    return z

s = input()
ans = set()
z = zfunc(s)
z[0] = len(s)
res = [0] * (len(s) + 1)

for i in z:
    res[i] += 1

from itertools import accumulate
res = [*accumulate(res[::-1])][::-1]

for i, j in enumerate(z[::-1]):
    if j > i:
        ans.add((j, res[j]))
print(len(ans))
for i in sorted([*ans]):
    print(*i)

s=input();n=len(s)
if n==1:
    print(1)
    print(1,1)
    quit()
priya=[-1]*n;q=-1
for i in range(1,n):
    while q>=0 and s[i]!=s[q+1]:
        q=priya[q]
    if s[i] == s[q + 1]:
        q+=1;priya[i]=q
cnt=[1]*n
for i in range(n-1,-1,-1):
    if priya[i]>=0:
        cnt[priya[i]]+=cnt[i]
Ans=[(n,1)];q=priya[n-1]
while q>=0:
    Ans.append((q+1,cnt[q]))
    q=priya[q]
Ans.sort()
print(len(Ans))
for i in Ans:print(*i)

def getLPS(s2,l):
  lps=[0]*l
  i=1
  j=0
  while i<l:
    if s2[i]==s2[j]:
       lps[i]=j+1 
       j+=1
       i+=1
       
    else:
      if j!=0:j=lps[j-1]
      else:
       lps[i]=0
       i+=1
  return lps
s=input()
n=len(s)
p=getLPS(s,n)
#print(p)
ans=[]
f=[0]*n
for i in range(n):
  f[p[i]]+=1
#print(f)
for i in range(n-1,0,-1):
  f[p[i-1]]+=f[i]
#print(f)
pos=n-1
ans=[[n,1]]
while pos>0:
  #print(pos)
  if p[pos]>1:
    ans.append([p[pos],f[p[pos]]+1])
  pos=p[pos]-1
 
if len(s)>1:
  f=s.count(s[0])
  if s[0]==s[len(s)-1]:
    ans.append([1,f])
print(len(ans))
for i in sorted(ans):
  print(i[0],i[1])


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

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[j] != s[i]:
            j = pi[j - 1]
        pi[i] = j + (s[j] == s[i])
    return pi

def solve(s):
    n = len(s)
    pi = prefix_function(s)
    j = n
    prefixes = []
    while j:
        prefixes.append(j)
        j = pi[j - 1]
    print(len(prefixes))
    if len(prefixes) == 1:
        print(n, 1)
        return
    cnt = [0] * (n + 1)
    for i in range(n):
        cnt[pi[i]] += 1
    for i in range(n - 1, 0, -1):
        cnt[pi[i - 1]] += cnt[i]
    for i in range(n + 1):
        cnt[i] += 1
    for i in reversed(prefixes):
        print(i, cnt[i])

def main():
    s = input()
    solve(s)

main()
    




import sys
input = sys.stdin.readline
from collections import deque

S=input().strip()


LEN=len(S)
i=1
j=0
A=[0]*LEN
A[0]=LEN

while i<LEN:
    while i+j<LEN and S[j]==S[i+j]:
        j+=1
    A[i]=j
    
    if j==0:
        i+=1
        continue
    
    k=1
    while i+k<LEN and k+A[k]<j:
        A[i+k]=A[k]
        k+=1
    i+=k
    j-=k

ANS=[0]*(LEN+1)

for a in A:
    ANS[a]+=1

for i in range(LEN-1,-1,-1):
    ANS[i]+=ANS[i+1]

ANS2=[]
for i in range(1,LEN+1):
    if A[LEN-i]==i:
        ANS2.append((i,ANS[i]))

print(len(ANS2))
for x,y in ANS2:
    print(x,y)





def computeLPSArray(pat, M, lps):
    len = 0
    lps[0]
    i = 1

    while i < M:
        if pat[i]== pat[len]:
            len += 1
            lps[i] = len
            i += 1
        else:
            if len != 0:
                len = lps[len-1]
            else:
                lps[i] = 0
                i += 1
    return lps

def count_subs_occ(s,m,l):
    occ=[0]*(m+1)

    for i in range(m):
        occ[l[i]]+=1

    for i in range(m-1,0,-1):
        occ[l[i-1]]+=occ[i]

    for i in range(m+1):
        occ[i]+=1

    return occ

s=input()
m=len(s)
l=[0]*m

x=computeLPSArray(s,m,l)
x=[0]+x
y=count_subs_occ(s,m,l)

a=x[-1]
if a==0:
    print(1)
    print(m,1)
elif a==1:
    print(2)
    print(1,y[a])
    print(m,1)
else:
    u=x[-1]
    v=x[u]
    ans=[[u,y[u]]]
    while(1):
        if v==0:
            break
        u=v
        v=x[u]
        temp=[u,y[u]]
        ans.append(temp)

    ans.sort()
    print(len(ans)+1)
    for i in range(len(ans)):
        print(ans[i][0],ans[i][1])
    print(m,1)