问题描述

给定一个长度为 $N$ 的字符串 $S$，由小写英文字母组成。$S$ 的第 $x$ 个字符（$1 \le x \le N$）记作 $S_x$。

对于每个 $i=1,2,\dots,N-1$，找到满足以下所有条件的最大非负整数 $l$：

• $l+i \le N$，且
• 对于所有整数 $k$（$1 \le k \le l$），都满足 $S_{k} \neq S_{k+i}$。

请注意，$l=0$ 总是满足这些条件。

约束条件

• $N$ 是一个满足 $2 \le N \le 5000$ 的整数。
• $S$ 是一个长度为 $N$ 的字符串，由小写英文字母组成。

输入

从标准输入中以以下格式给出：

$N$ $S$

输出

输出 $(N-1)$ 行。第 $x$ 行（$1 \le x < N$）应该包含当 $i=x$ 时的答案作为一个整数。

示例输入1

6
abcbac

示例输出1

5
1
2
0
1

在这个示例中，$S=$ abcbac。

• 当 $i=1$ 时，我们有 $S_1 \neq S_2, S_2 \neq S_3, \dots$，并且 $S_5 \neq S_6$，因此最大值为 $l=5$。
• 当 $i=2$ 时，我们有 $S_1 \neq S_3$ 但是 $S_2 = S_4$，因此最大值为 $l=1$。
• 当 $i=3$ 时，我们有 $S_1 \neq S_4$ 并且 $S_2 \neq S_5$ 但是 $S_3 = S_6$，因此最大值为 $l=2$。
• 当 $i=4$ 时，我们有 $S_1 = S_5$，因此最大值为 $l=0$。
• 当 $i=5$ 时，我们有 $S_1 \neq S_6$，因此最大值为 $l=1$。