**Замечание: ограничение по памяти для этой задачи 512MB,
что в два раза больше значения по умолчанию.**
После многих лет побед Беси в играх, Фермер Джон решил, что это неслучайно.
Он решил, что в DNA Беси есть ген "победы в играх", поэтому он решил найти этот ген.
ФД разработал такой процесс идентификации возможных кандидатов на
"ген побед". Он взял геном Беси, который представляется строкой \(S\) длины \(N\),
где \(1 \leq N \leq 3000\). Он выбирает некоторую пару
pair \((K,L)\) где \(1 \leq L \leq K \leq N\), представляющую, что кандидаты
на "ген побед" имеют длину \(L\) и находятся среди подстрок длиной больше \(K\).
Чтобы идентифицировать ген, он все подстроки длины \(K\) и называет их \(k\)-mer.
Для заданного \(k\)-mer, он берёт все подстроки длины \(L\), находит
лексикографически минимальную как кандидат на "ген побед" (выбирая самую левую
такую подстроку, если их несколько) и затем выписывает индексируемую с \(0\)
позицию \(p_i\) такую, что эта подстрока начинается в строке в позиции \(p_i\) и заносит в множество
\(P\).
ФД хочет узнать, сколько будет кандидатов на "ген победы" для каждой
пары \((K,L)\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Гарантируется, что все символы - большие латинские буквы в интервале
\(s_i \in A-Z\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого \(v\) в интервале \(1\dots N\), введите на отдельной строке
количество пар, таких что \(|P|=v\),
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
AGTCAACG
|
11
10
5
4
2
2
1
1
|