Nachdem Farmer John jahrelang Spiele veranstaltet und Bessie immer wieder den ersten Platz belegen gesehen hat, erkennt er, dass dies kein Zufall sein kann. Er schließt daraus, dass das Gewinnen in ihrer DNA codiert sein muss, und sucht dieses „Gewinner“-Gen.

Er entwickelt ein Verfahren, um mögliche Kandidaten für dieses Gen zu bestimmen. Bessies Genom ist eine Zeichenkette $S$ der Länge $N$ mit $1 \leq N \leq 3000$. Er wählt ein Paar $(K,L)$ mit $1 \leq L \leq K \leq N$. Die Genkandidaten sollen Länge $L$ haben und in einem größeren Teilstring der Länge $K$ gefunden werden. Er betrachtet alle Teilstrings der Länge $K$ von $S$, die wir jeweils einen $k$-mer nennen. Für jeden $k$-mer betrachtet er alle Teilstrings der Länge $L$ und wählt den lexikographisch kleinsten als Genkandidaten (bei Gleichstand den am weitesten links liegenden). Dann fügt er dessen Startposition $p_i$ in $S$, mit Indizes ab $0$, einer Menge $P$ hinzu.

Da er $K$ und $L$ noch nicht gewählt hat, möchte er die Anzahl der Kandidaten für jedes Paar $(K,L)$ kennen.

Hilf ihm, für jedes $v$ in $1\dots N$ die Anzahl der Paare $(K,L)$ mit $|P|=v$ zu bestimmen.

Eingabe

$N$ bezeichnet die Länge der Zeichenkette und $S$ die gegebene Zeichenkette. Alle Zeichen sind garantiert Großbuchstaben mit $s_i \in A-Z$, da die Rindergenetik viel weiter fortgeschritten ist als unsere.

Ausgabe

Gib für jedes $v$ in $1\dots N$ die Anzahl der Paare $(K,L)$ mit $|P|=v$ aus, jeweils in einer eigenen Zeile.

Beispiele

Eingabe 1

8
AGTCAACG

Ausgabe 1

11
10
5
4
2
2
1
1

Hinweis

Die dritte Ausgabezeile dieses Testfalls ist 5, weil genau 5 Paare von $K$ und $L$ drei „Gewinner“-Genkandidaten ergeben. Diese Kandidaten sind folgende ($p_i$ ist ab $0$ indiziert):

(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]

Um zu sehen, wie (4,2) diese Ergebnisse liefert, betrachten wir alle $4$-mer:

AGTC
GTCA
TCAA
CAAC
AACG

Für jeden $4$-mer bestimmen wir den lexikographisch kleinsten Teilstring der Länge 2:

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

Wir fügen die Positionen dieser Teilstrings in der ursprünglichen Zeichenkette einer Menge $P$ hinzu und erhalten $P = [0,3,4]$.

Das Paar $(4,1)$ ergibt dagegen insgesamt nur $2$ „Gewinner“-Genkandidaten. Wenn wir alle $4$-mer betrachten und jeweils den lexikographisch kleinsten Teilstring der Länge $1$ bestimmen (mit A, A' und A* zur Unterscheidung verschiedener A), erhalten wir:

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

In den letzten 3 Fällen sind A' und A* beide lexikographisch minimal, aber der am weitesten links liegende Teilstring hat Vorrang. Deshalb zählt jeweils nur A' als Kandidat. Somit ist $P = [0,4]$.

Teilaufgaben

• Eingaben 2-4: $N \leq 100$
• Eingaben 5-7: $N \leq 500$
• Eingaben 8-16: keine zusätzlichen Einschränkungen.

Aufgabenautor: Suhas Nagar