Po latach organizowania gier i obserwowania, jak Bessie raz za razem zajmuje pierwsze miejsce, Farmer John zrozumiał, że to nie przypadek. Uznał, że wygrywanie musi być zapisane w jej DNA, i postanowił znaleźć ten „zwycięski” gen.

Opracował procedurę znajdowania jego możliwych kandydatów. Genom Bessie to napis $S$ długości $N$, gdzie $1 \leq N \leq 3000$. Wybiera parę $(K,L)$ z $1 \leq L \leq K \leq N$, oznaczającą, że geny kandydujące mają długość $L$ i są szukane wewnątrz większego podnapisu długości $K$. Bierze wszystkie podnapisy długości $K$ napisu $S$, każdy nazywany $k$-merem. Dla każdego $k$-meru rozpatruje wszystkie podnapisy długości $L$ i wybiera najmniejszy leksykograficznie jako gen kandydujący (najbardziej z lewej w razie remisu). Następnie dodaje do zbioru $P$ pozycję $p_i$ jego początku w $S$, indeksowaną od $0$.

Ponieważ nie wybrał jeszcze $K$ i $L$, chce znać liczbę kandydatów dla każdej pary $(K,L)$.

Dla każdego $v$ z $1\dots N$ pomóż ustalić liczbę par $(K,L)$ z $|P|=v$.

Wejście

$N$ oznacza długość napisu, a $S$ podany napis. Wszystkie znaki są gwarantowanie wielkimi literami, $s_i \in A-Z$, ponieważ genetyka bydła jest znacznie bardziej zaawansowana niż nasza.

Wyjście

Dla każdego $v$ z $1\dots N$ wypisz liczbę par $(K,L)$ z $|P|=v$, każdą liczbę w osobnym wierszu.

Przykład

Wejście 1

8
AGTCAACG

Wyjście 1

11
10
5
4
2
2
1
1

Uwagi

Trzeci wiersz wyjścia w tym teście to 5, bo dokładnie 5 par $K$ i $L$ daje trzy „zwycięskie” geny kandydujące. Kandydaci są następujący ($p_i$ jest indeksowane od $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]

Aby zobaczyć, jak (4,2) daje te wyniki, bierzemy wszystkie $4$-mery:

AGTC
GTCA
TCAA
CAAC
AACG

Dla każdego $4$-meru wybieramy najmniejszy leksykograficznie podnapis długości 2:

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

Dodajemy pozycje tych podnapisów w pierwotnym napisie do zbioru $P$, uzyskując $P = [0,3,4]$.

Z kolei para $(4,1)$ daje łącznie tylko $2$ „zwycięskie” geny kandydujące. Biorąc wszystkie $4$-mery i wybierając najmniejszy leksykograficznie podnapis długości $1$ (używając A, A' i A* do rozróżnienia różnych A), otrzymujemy:

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

Choć w ostatnich 3 przypadkach zarówno A', jak i A* są najmniejsze leksykograficznie, pierwszeństwo ma podnapis najbardziej z lewej. Dlatego w każdym z tych przypadków tylko A' liczy się jako kandydat. Zatem $P = [0,4]$.

Podzadania

• Wejścia 2-4: $N \leq 100$
• Wejścia 5-7: $N \leq 500$
• Wejścia 8-16: brak dodatkowych ograniczeń.

Autor zadania: Suhas Nagar