举办多年的比赛，眼看 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