Дана строка 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.