您有一个字符串 s = s1s2...s|s|,其中 |s|是字符串 s 的长度,si 是第 i 个字符。
我们先介绍几个定义:
- 字符串 s 的子字符串 s[i..j] (1 ≤ i ≤ j ≤ |s|) 是字符串 sisi + 1...sj。
- 长度为 l (1 ≤ l ≤ |s|) 的字符串 s 的前缀是字符串 s[1..l]。
- 长度为 l (1 ≤ l ≤ |s|) 的字符串 s 的后缀是字符串 s[|s| - l + 1..|s|]。
你的任务是,对于与字符串 s 的后缀匹配的字符串 s 的任何前缀,打印它作为子字符串在字符串 s 中出现的次数。
输入
单行包含字符序列 s1s2...s|s| (1 ≤ |s| ≤ 105) — 字符串 s。该字符串仅由大写英文字母组成。
输出
在第一行中,打印整数 k (0 ≤ k ≤ |s|) — 与字符串 s 的后缀匹配的前缀数量。接下来打印k行,每行打印两个整数li ci。数字li ci 表示长度为li 的前缀与长度为li 的后缀匹配,并作为子串ci 出现在字符串s 中。按 li 递增的顺序打印 li ci 对。
示例
输入 #1
ABACABA
输出 #1
3 1 4 3 2 7 1
输入 #2
AAA
输出 #2
3 1 3 2 2 3 1