D. Префиксы и суффиксы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка s = s1s2...s|s|, где |s| — длина строки s, а si — ее i-й символ.

Введем несколько определений:

  • Подстрокой s[i..j] (1 ≤ i ≤ j ≤ |s|) строки s называется строка sisi + 1...sj.
  • Префиксом строки s длины l (1 ≤ l ≤ |s|) называется строка s[1..l].
  • Суффиксом строки s длины l (1 ≤ l ≤ |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 и встречается в строке s в качестве подстроки ci раз. Пары li ci выводите в порядке возрастания li.

Примеры
Входные данные
ABACABA
Выходные данные
3
1 4
3 2
7 1
Входные данные
AAA
Выходные данные
3
1 3
2 2
3 1