Дана строка 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 как подстрока.
Выходные данные
В первой строке выведите целое число k (0 ≤ k ≤ |s|) — количество префиксов, которые совпадают с суффиксом строки s. Далее выведите k строк, в каждой строке выведите два целых числа li ci. Числа li ci обозначают, что префикс длины li совпадает с суффиксом длины li и встречается в строке s в качестве подстроки ci раз. Пары li ci выводите в порядке возрастания li.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ABACABA
|
3
1 4
3 2
7 1
|
|
2
|
AAA
|
3
1 3
2 2
3 1
|