Dopo anni a organizzare giochi e vedere Bessie arrivare prima di continuo, Farmer John capisce che non può essere un caso. Conclude che la vittoria deve essere codificata nel suo DNA e cerca questo gene «vincente».

Progetta una procedura per identificarne i possibili candidati. Il genoma di Bessie è una stringa $S$ di lunghezza $N$, dove $1 \leq N \leq 3000$. Sceglie una coppia $(K,L)$ con $1 \leq L \leq K \leq N$, indicando che i geni candidati avranno lunghezza $L$ e saranno cercati in una sottostringa più grande di lunghezza $K$. Prende tutte le sottostringhe di lunghezza $K$ di $S$, ciascuna chiamata $k$-mer. Per ogni $k$-mer esamina tutte le sottostringhe di lunghezza $L$ e sceglie la minima lessicograficamente come gene candidato (la più a sinistra in caso di parità). Poi aggiunge a un insieme $P$ la sua posizione iniziale $p_i$ in $S$, indicizzata a partire da $0$.

Poiché non ha ancora scelto $K$ e $L$, vuole sapere quanti candidati ci saranno per ogni coppia $(K,L)$.

Per ogni $v$ in $1\dots N$, aiutalo a determinare il numero di coppie $(K,L)$ con $|P|=v$.

Input

$N$ rappresenta la lunghezza della stringa e $S$ la stringa data. È garantito che tutti i caratteri siano maiuscoli, con $s_i \in A-Z$, perché la genetica bovina è molto più avanzata della nostra.

Output

Per ogni $v$ in $1\dots N$, stampa il numero di coppie $(K,L)$ con $|P|=v$, ciascun numero su una riga separata.

Esempi

Input 1

8
AGTCAACG

Output 1

11
10
5
4
2
2
1
1

Spiegazione

In questo caso, la terza riga dell'output vale 5 perché esistono esattamente 5 coppie di $K$ e $L$ che producono tre geni «vincenti» candidati. I candidati sono i seguenti ($p_i$ è indicizzato da $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]

Per vedere come (4,2) produce questi risultati, prendiamo tutti i $4$-mer:

AGTC
GTCA
TCAA
CAAC
AACG

Per ogni $4$-mer identifichiamo la sottostringa di lunghezza 2 minima lessicograficamente:

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

Aggiungiamo a un insieme $P$ le posizioni di queste sottostringhe nella stringa originale, ottenendo $P = [0,3,4]$.

Invece, la coppia $(4,1)$ produce solo $2$ geni «vincenti» candidati in totale. Prendendo tutti i $4$-mer e scegliendo la sottostringa di lunghezza $1$ minima lessicograficamente (usando A, A' e A* per distinguere le varie A), otteniamo:

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

Negli ultimi 3 casi A' e A* sono entrambe minime lessicograficamente, ma ha precedenza la sottostringa più a sinistra, quindi A' è l'unico candidato contato in tutti questi casi. Pertanto $P = [0,4]$.

Punteggio

• Input 2-4: $N \leq 100$
• Input 5-7: $N \leq 500$
• Input 8-16: nessun vincolo aggiuntivo.

Autore del problema: Suhas Nagar