После многих лет проведения игр и наблюдений за тем, как Bessie снова и снова занимает первое место, Farmer John понял, что это не случайность. Он решил, что победа должна быть закодирована в её ДНК, и начал искать этот «победный» ген.

Он разработал процедуру поиска возможных кандидатов. Геном Bessie — строка $S$ длины $N$, где $1 \leq N \leq 3000$. Он выбирает пару $(K,L)$ с $1 \leq L \leq K \leq N$, означающую, что гены-кандидаты имеют длину $L$ и ищутся внутри большей подстроки длины $K$. Он берёт все подстроки длины $K$ строки $S$, каждую из которых назовём $k$-мером. Для каждого $k$-мера он рассматривает все подстроки длины $L$ и выбирает лексикографически минимальную как победный ген-кандидат (при равенстве самую левую). Затем он добавляет в множество $P$ позицию $p_i$ её начала в $S$, с индексацией от $0$.

Поскольку он ещё не выбрал $K$ и $L$, ему нужно знать число кандидатов для каждой пары $(K,L)$.

Для каждого $v$ из $1\dots N$ помогите определить число пар $(K,L)$ с $|P|=v$.

Входные данные

$N$ обозначает длину строки, а $S$ — заданную строку. Все символы гарантированно заглавные, $s_i \in A-Z$, ведь генетика коров гораздо совершеннее нашей.

Выходные данные

Для каждого $v$ из $1\dots N$ выведите число пар $(K,L)$ с $|P|=v$, каждое число на отдельной строке.

Примеры

Входные данные 1

8
AGTCAACG

Выходные данные 1

11
10
5
4
2
2
1
1

Примечание

В этом тесте третья строка вывода равна 5, поскольку ровно 5 пар $K$ и $L$ дают три «победных» гена-кандидата. Кандидаты приведены ниже ($p_i$ индексируется от $0$):

(4,2) -> P = [0,3,4]
(5,3) -> P = [0,3,4]
(6,4) -> P = [0,3,4]
(6,5) -> P = [0,1,3]
(6,6) -> P = [0,1,2]

Чтобы увидеть, как (4,2) даёт эти результаты, возьмём все $4$-меры:

AGTC
GTCA
TCAA
CAAC
AACG

Для каждого $4$-мера определим лексикографически минимальную подстроку длины 2:

AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA

Добавим позиции всех этих подстрок в исходной строке в множество $P$ и получим $P = [0,3,4]$.

С другой стороны, пара $(4,1)$ даёт всего $2$ «победных» гена-кандидата. Если взять все $4$-меры и выбрать лексикографически минимальную подстроку длины $1$ (используя A, A' и A* для различения разных A), получим:

AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'

В последних 3 случаях и A', и A* лексикографически минимальны, но самая левая подстрока имеет приоритет. Поэтому во всех этих случаях только A' считается кандидатом. Значит, $P = [0,4]$.

Подзадачи

• Входы 2-4: $N \leq 100$
• Входы 5-7: $N \leq 500$
• Входы 8-16: без дополнительных ограничений.

Автор задачи: Suhas Nagar