时间限制：1秒　　内存限制：256M

---

【问题描述】

　　在多年举办比赛并看着 Bessie 一次又一次地获得第一名后，Farmer John 意识到这绝非偶然。他得出结论，Bessie 一定将胜利写进了 DNA，于是他开始寻找这种「胜利」基因。

　　他设计了一个过程来识别这个「胜利」基因的可能候选。他获取了 Bessie 的基因组，为一个长为 \(N（1≤N≤3000）\) 的字符串 \(S\)，其中 。他选择某个数对 \((K,L)\)，其中 \(1≤L≤K≤N\)，表示「胜利」基因候选的长度将为 L，并且将在一个较大的 K 长度子串中进行寻找。为了识别这一基因，他从 \(S\) 中取出所有 \(K\) 长度的子串，我们将称这样的子串为一个 K-mer。对于一个给定的 K-mer，他取出其所有长度为 \(L\) 的子串，将字典序最小的子串识别为胜利基因候选（如果存在并列则选择其中最左边的子串），然后将该字串在 \(S\) 中的起始位置 \(p_i\)（从 0 开始索引）写入一个集合 \(P\)。

　　由于他还没有选定 \(K\) 和 \(L\)，他想知道每对 \((K,L)\) 将有多少个候选。对于 \(1..N\) 中的每一个 \(v\)，帮助他求出满足 \(∣P∣=v\) 的 \((K,L)\) 对的数量。

【输入格式】

　　输入的第一行包含 \(N\)，为字符串的长度。
　　第二行包含 \(S\)，为给定的字符串。输入保证所有字符均为大写字符，其中 \(s_i ∈A−Z\)，因为奶牛遗传学远比我们的高级。

【输出格式】

　　对于 \(1..N\) 中的每一个 \(v\)，输出满足 \(∣P∣=v\) 的 \((K,L)\) 对的数量，每行输出一个数。

【输入输出样例】

　Input

8
AGTCAACG

　Output

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'
尽管 A' 和 A* 在最后 3 种情况下字典序均为最小，但最左边的子串优先，因此仅有 A' 在所有这些情况中被视为候选。这意味着 \(P=\)[0,4]。

【测试点性质】

　　测试点 \(2−4：N≤100\)。
　　测试点 \(5−7：N≤500\)。
　　测试点 \(8−16：\)没有额外限制。

【来源】

　　Mr.he