Given a string 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. Expected Complexity: O(n)
Input Format
The first line contains string s.
Output Format
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.
Constraints
1<= s.length() <= 10^5
Example
Input
ABABABAB
Output
4 2 4 4 3 6 2 8 1