题目描述

给定一个字符串 $s = s_{1}s_{2}\ldots s_{|s|}$ ，其中 $|s|$ 表示字符串 $s$ 的长度， $s_{i}$ 表示它的第 $i$ 个字符。

我们引入以下几个定义：

字符串 $s$ 的一个子串 $s[i..j]$ $(1 \leq i \leq j \leq |s|)$ 指的是字符串 $s_{i}s_{i+1}\ldots s_{j}$ 。
字符串 $s$ 长度为 $l$ 的前缀 $(1 \leq l \leq |s|)$ 为 $s[1..l]$ 。
字符串 $s$ 长度为 $l$ 的后缀 $(1 \leq l \leq |s|)$ 为 $s[|s|-l+1..|s|]$ 。

你的任务是，对于所有前缀等于后缀的长度 $l$ ，输出它在字符串 $s$ 中作为子串出现的次数。

输入格式

一行，包括一个只由大写英文字母组成的字符串 $s$ $(1 \leq |s| \leq 10^{5})$ 。

第一行输出一个整数 $k$ $(0 \leq k \leq |s|)$ ，表示有多少个前缀等于后缀。

接下来 $k$ 行，每行输出两个整数 $l_{i}\ c_{i}$ ，表示长度为 $l_{i}$ 的前缀与后缀相等，并且它在字符串 $s$ 中作为子串出现了 $c_{i}$ 次。请按照 $l_{i}$ 递增的顺序输出每组数据。

ABACABA

AAA