舉辦多年的比賽，眼看 Bessie 一次又一次獲得第一名，Farmer John 意識到這不可能是巧合。他認定 Bessie 的 DNA 一定編碼了勝利，因此開始尋找這個「勝利」基因。

他設計了一個尋找「勝利」基因候選者的過程。Bessie 的基因組是一個長度為 $N$ 的字串 $S$，其中 $1 \leq N \leq 3000$。他選取一對 $(K,L)$，滿足 $1 \leq L \leq K \leq N$，表示「勝利」基因候選者長度為 $L$，並在一個更長、長度為 $K$ 的子字串中尋找。為識別基因，他取出 $S$ 中全部長度為 $K$ 的子字串，稱為 $k$-mer。對每個 $k$-mer，他取出其中全部長度為 $L$ 的子字串，把字典序最小的子字串確定為一個勝利基因候選者（若有多個，則選最靠左的那個），然後將該子字串在 $S$ 中的起始位置 $p_i$（從 $0$ 開始編號）加入集合 $P$。

由於他尚未選定 $K$ 和 $L$，他想知道每對 $(K,L)$ 會產生多少候選者。

對於 $1\dots N$ 中的每個 $v$，請幫他確定滿足 $|P|=v$ 的 $(K,L)$ 對數。

輸入格式

$N$ 表示字串長度，$S$ 表示給定字串。保證所有字元都是大寫字母，即 $s_i \in A-Z$，因為牛的遺傳學遠比人類的先進。

輸出格式

對於 $1\dots N$ 中的每個 $v$，輸出滿足 $|P|=v$ 的 $(K,L)$ 對數，每個數占一行。

範例

輸入格式 1

8
AGTCAACG

輸出格式 1

11
10
5
4
2
2
1
1

說明

這個測試案例中，輸出的第三行為 5，因為恰有 5 對 $K$ 和 $L$ 會產生三個「勝利」基因候選者。候選者如下（$p_i$ 從 $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]

要看 (4,2) 如何得到這些結果，先取出全部 $4$-mer：

AGTC
GTCA
TCAA
CAAC
AACG

對於每個 $4$-mer，找出字典序最小的長度為 2 的子字串：

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

取出這些子字串在原字串中的位置，加入集合 $P$，得到 $P = [0,3,4]$。

另一方面，若考察 $(4,1)$，則只會產生總共 $2$ 個「勝利」基因候選者。取出所有 $4$-mer 並找出字典序最小的長度為 $1$ 的子字串（用 A、A' 和 A* 區分不同的 A），得到：

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

最後 3 種情況中，A' 和 A* 都是字典序最小的子字串，但最靠左的子字串優先，所以這些情況下都只有 A' 被算作候選者。因此 $P = [0,4]$。

子任務

• 輸入 2-4：$N \leq 100$
• 輸入 5-7：$N \leq 500$
• 輸入 8-16：無額外限制。

題目作者：Suhas Nagar