CF432D.Prefixes and Suffixes

You have a string s = _s_1_s_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.

你有一个字符串 $s = s_1s_2\ldots s_{|s|}$，其中 $|s|$ 表示字符串 $s$ 的长度，$s_i$ 表示 $s$ 的第 $i$ 个字符。

我们引入如下定义：

• 字符串 $s$ 的子串 $s[i..j]$（其中 $1 \le i \le j \le |s|$）定义为字符串 $s_is_{i+1}\ldots s_j$。
• 字符串 $s$ 长度为 $l$（其中 $1 \le l \le |s|$）的前缀定义为字符串 $s[1..l]$。
• 字符串 $s$ 长度为 $l$（其中 $1 \le l \le |s|$）的后缀定义为字符串 $s[|s| - l + 1..|s|]$。

你的任务是：对字符串 $s$ 的每一个既是前缀又是后缀的子串，输出它在 $s$ 中作为子串出现的总次数。

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

单行包含一个字符序列 $s_1s_2\ldots s_{|s|}$（$1 \le |s| \le 10^5$）——字符串 $s$。该字符串仅由大写英文字母组成。

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.

第一行输出一个整数 $k$（$0 \leq k \leq |s|$），表示字符串 $s$ 中与某个后缀相匹配的前缀个数。接下来输出 $k$ 行，每行输出两个整数 $l_i$ 和 $c_i$。其中 $l_i$ 和 $c_i$ 表示长度为 $l_i$ 的前缀与长度为 $l_i$ 的后缀相匹配，并且该前缀作为子串在字符串 $s$ 中共出现 $c_i$ 次。请按 $l_i$ 递增的顺序输出所有数对 $(l_i, c_i)$。