Après des années à organiser des jeux et à voir Bessie terminer première à répétition, Farmer John comprend que ce ne peut pas être un hasard. Il conclut que la victoire doit être inscrite dans son ADN et entreprend de trouver ce gène « gagnant ».

Il conçoit un procédé pour identifier des candidats à ce gène. Le génome de Bessie est une chaîne $S$ de longueur $N$, où $1 \leq N \leq 3000$. Il choisit une paire $(K,L)$ avec $1 \leq L \leq K \leq N$, signifiant que les gènes candidats auront une longueur $L$ et seront recherchés dans une sous-chaîne plus grande de longueur $K$. Il prend toutes les sous-chaînes de longueur $K$ de $S$, chacune appelée un $k$-mer. Pour chaque $k$-mer, il examine toutes les sous-chaînes de longueur $L$, choisit la plus petite dans l'ordre lexicographique comme gène candidat (la plus à gauche en cas d'égalité), puis ajoute à un ensemble $P$ sa position de début $p_i$ dans $S$, indexée à partir de $0$.

Comme il n'a pas encore choisi $K$ et $L$, il souhaite connaître le nombre de candidats pour chaque paire $(K,L)$.

Pour chaque $v$ dans $1\dots N$, aidez-le à déterminer le nombre de paires $(K,L)$ telles que $|P|=v$.

Entrée

$N$ représente la longueur de la chaîne et $S$ la chaîne donnée. Tous les caractères sont garantis majuscules, avec $s_i \in A-Z$, car la génétique bovine est bien plus avancée que la nôtre.

Sortie

Pour chaque $v$ dans $1\dots N$, affichez le nombre de paires $(K,L)$ telles que $|P|=v$, chaque nombre sur une ligne séparée.

Exemples

Entrée 1

8
AGTCAACG

Sortie 1

11
10
5
4
2
2
1
1

Remarque

Dans ce cas, la troisième ligne de sortie vaut 5, car exactement 5 paires de $K$ et $L$ donnent trois gènes « gagnants » candidats. Ces candidats sont les suivants ($p_i$ est indexé à 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]

Pour voir comment (4,2) donne ces résultats, prenons tous les $4$-mers :

AGTC
GTCA
TCAA
CAAC
AACG

Pour chaque $4$-mer, choisissons la sous-chaîne de longueur 2 minimale dans l'ordre lexicographique :

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

Ajoutons à un ensemble $P$ les positions de ces sous-chaînes dans la chaîne d'origine. Nous obtenons $P = [0,3,4]$.

En revanche, la paire $(4,1)$ donne seulement $2$ gènes « gagnants » candidats au total. Si nous choisissons, dans chaque $4$-mer, la sous-chaîne de longueur $1$ minimale dans l'ordre lexicographique (en utilisant A, A' et A* pour distinguer les différents A), nous obtenons :

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

Dans les 3 derniers cas, A' et A* sont tous deux minimaux dans l'ordre lexicographique, mais la sous-chaîne la plus à gauche est prioritaire. A' est donc le seul candidat compté dans chacun de ces cas. Ainsi, $P = [0,4]$.

Sous-tâches

• Entrées 2-4 : $N \leq 100$
• Entrées 5-7 : $N \leq 500$
• Entrées 8-16 : aucune contrainte supplémentaire.

Auteur du problème : Suhas Nagar