Depois de anos organizando jogos e vendo Bessie ficar em primeiro lugar repetidamente, Farmer John percebe que isso não pode ser acidental. Conclui que vencer deve estar codificado em seu DNA e tenta encontrar esse gene «vencedor».

Ele cria um processo para identificar possíveis candidatos a esse gene. O genoma de Bessie é uma string $S$ de comprimento $N$, onde $1 \leq N \leq 3000$. Ele escolhe um par $(K,L)$ com $1 \leq L \leq K \leq N$, indicando que os genes candidatos terão comprimento $L$ e serão encontrados dentro de uma substring maior de comprimento $K$. Ele toma todas as substrings de comprimento $K$ de $S$, cada uma chamada de $k$-mer. Para cada $k$-mer, examina todas as substrings de comprimento $L$, escolhe a lexicograficamente mínima como gene candidato (a mais à esquerda em caso de empate) e adiciona a um conjunto $P$ sua posição inicial $p_i$ em $S$, indexada a partir de $0$.

Como ainda não escolheu $K$ e $L$, quer saber quantos candidatos haverá para cada par $(K,L)$.

Para cada $v$ em $1\dots N$, ajude-o a determinar o número de pares $(K,L)$ com $|P|=v$.

Entrada

$N$ representa o comprimento da string e $S$ a string dada. Todos os caracteres são garantidamente maiúsculos, com $s_i \in A-Z$, pois a genética bovina é muito mais avançada que a nossa.

Saída

Para cada $v$ em $1\dots N$, imprima o número de pares $(K,L)$ com $|P|=v$, cada número em uma linha separada.

Exemplos

Entrada 1

8
AGTCAACG

Saída 1

11
10
5
4
2
2
1
1

Nota

Neste caso, a terceira linha da saída é 5, pois exatamente 5 pares de $K$ e $L$ geram três genes «vencedores» candidatos. Os candidatos são os seguintes ($p_i$ é indexado a partir de $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]

Para ver como (4,2) produz esses resultados, tomamos todos os $4$-mers:

AGTC
GTCA
TCAA
CAAC
AACG

Para cada $4$-mer, identificamos a substring de comprimento 2 lexicograficamente mínima:

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

Adicionamos as posições dessas substrings na string original a um conjunto $P$, obtendo $P = [0,3,4]$.

Por outro lado, o par $(4,1)$ produz apenas $2$ genes «vencedores» candidatos no total. Tomando todos os $4$-mers e identificando a substring de comprimento $1$ lexicograficamente mínima (usando A, A' e A* para distinguir os diferentes A), obtemos:

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

Embora A' e A* sejam ambas lexicograficamente mínimas nos últimos 3 casos, a substring mais à esquerda tem prioridade. Assim, somente A' é contada como candidata em todos esses casos. Portanto, $P = [0,4]$.

Pontuação

• Entradas 2-4: $N \leq 100$
• Entradas 5-7: $N \leq 500$
• Entradas 8-16: sem restrições adicionais.

Autor do problema: Suhas Nagar