题目描述

给定一个字符串 $s = s_1 s_2 \ldots s_{|s|}$。这里 $|s|$ 表示字符串 $s$ 的长度，我们用 $s_i$ 表示字符串 $s$ 中的第 $i$ 个字符。

我们有如下定义：

• 字符串的子串 $s[i..j](1 \le i \le j \le |s|)$ 表示的是 $s_i s_{i+1} \ldots s_j$
• 字符串的长度为 $l(1 \le l \le |s|)$ 的前缀指的是子串 $s[1..l]$
• 字符串的长度为 $l(1 \le l \le |s|)$ 的后缀指的是字符串 $s[|s|-l+1..|s|]$

你的任务是：对于任意一个长度 $l$，在长度为 $l$ 的前缀等于长度为 $l$ 的后缀的情况下，字符串 $s$ 中存在多少个长度为 $l$ 的子串等于前缀。

输入格式

输入共一行，包含一个字符串 $s_1 s_2 \ldots s_|s|(1 \le |s| \le 10^5)$。数据保证字符串仅由大写英文字母组成。

输出格式

输出的第一行包含一个整数 $k(0 \le k \le |s|)$，表示前缀和后缀能够匹配上的长度有多少个。

接下来 $k$ 行，每行包含两个整数 $l_i$ 和 $c_i$，以一个空格分隔。其中 $l_i$ 表示前缀长度（即要求长度为 $l_i$ 的前缀等于长度为 $l_i$ 的后缀），$c_i$ 表示字符串中存在多少个子串等于长度为 $l_i$ 的前缀。

要求按照 $l_i$ 递增的顺序输出所有 $l_i$ 和 $c_i$。

样例

ABACABA

3
1 4
3 2
7 1

AAA

3
1 3
2 2
3 1

说明/提示

样例解释

样例1：

• 当 $l_1 = 1$ 时，满足条件的子串有 $s[1..1] = s[3..3] = s[5..5] = s[7..7] =$ 'A'
• 当 $l_2 = 3$ 时，满足条件的子串有 $s[1..3] = s[4..7] =$ 'ABA'
• 当 $l_3 = 7$ 时，满足条件的子串有 $s[1..7] =$ 'ABACABA'

样例2：

• 当 $l_1 = 1$ 时，满足条件的子串有 $s[1..1] = s[2..2] = s[3..3] =$ 'A'
• 当 $l_2 = 2$ 时，满足条件的子串有 $s[1..2] = s[2..3] =$ 'AA'
• 当 $l_3 = 3$ 时，满足条件的子串有 $s[1..3] =$ 'AAA'

数据规模与约定

• 对于 $30\%$ 的数据，$|s| \le 100$
• 对于 $60\%$ 的数据，$|s| \le 10^4$
• 对于 $100\%$ 的数据，$1 \le |s| \le 10^5$