Tras años organizando juegos y viendo a Bessie quedar primera una y otra vez, Farmer John se da cuenta de que no puede ser casualidad. Concluye que ganar debe estar codificado en su ADN y se propone encontrar ese gen «ganador».

Diseña un proceso para identificar candidatos a ese gen. El genoma de Bessie es una cadena $S$ de longitud $N$, donde $1 \leq N \leq 3000$. Elige un par $(K,L)$ con $1 \leq L \leq K \leq N$, que indica que los genes candidatos tendrán longitud $L$ y se buscarán dentro de una subcadena mayor de longitud $K$. Toma todas las subcadenas de longitud $K$ de $S$, cada una llamada $k$-mer. Para cada $k$-mer examina todas las subcadenas de longitud $L$, elige la mínima lexicográficamente como gen candidato (la más a la izquierda en caso de empate) y añade a un conjunto $P$ su posición inicial $p_i$ en $S$, indexada desde $0$.

Como aún no ha elegido $K$ y $L$, quiere saber cuántos candidatos habrá para cada par $(K,L)$.

Para cada $v$ en $1\dots N$, ayúdalo a determinar el número de pares $(K,L)$ con $|P|=v$.

Entrada

$N$ representa la longitud de la cadena y $S$ la cadena dada. Se garantiza que todos los caracteres son mayúsculas, con $s_i \in A-Z$, porque la genética bovina está mucho más avanzada que la nuestra.

Salida

Para cada $v$ en $1\dots N$, imprime el número de pares $(K,L)$ con $|P|=v$, cada número en una línea separada.

Ejemplos

Entrada 1

8
AGTCAACG

Salida 1

11
10
5
4
2
2
1
1

Nota

En este caso, la tercera línea de salida es 5 porque exactamente 5 pares de $K$ y $L$ dan tres genes «ganadores» candidatos. Estos candidatos son los siguientes ($p_i$ está indexado desde $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 cómo (4,2) produce estos resultados, tomamos todos los $4$-mers:

AGTC
GTCA
TCAA
CAAC
AACG

Para cada $4$-mer, identificamos la subcadena de longitud 2 mínima lexicográficamente:

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

Añadimos las posiciones de estas subcadenas en la cadena original a un conjunto $P$ para obtener $P = [0,3,4]$.

En cambio, el par $(4,1)$ produce solo $2$ genes «ganadores» candidatos en total. Si tomamos todos los $4$-mers e identificamos la subcadena de longitud $1$ mínima lexicográficamente (usando A, A' y A* para distinguir las distintas A), obtenemos:

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

Aunque A' y A* son ambas mínimas lexicográficamente en los 3 últimos casos, la subcadena más a la izquierda tiene prioridad, por lo que A' es el único candidato contado en todos ellos. Así, $P = [0,4]$.

Subtareas

• Entradas 2-4: $N \leq 100$
• Entradas 5-7: $N \leq 500$
• Entradas 8-16: sin restricciones adicionales.

Autor del problema: Suhas Nagar