問題文

英小文字からなる長さ $N$ の文字列 $S$ が与えられます。 $S$ の $x$ 文字目 $(1 \\le x \\le N)$ は $S_x$ です。

$i=1,2,\\dots,N-1$ それぞれについて、以下の条件を全て満たす最大の非負整数 $l$ を求めてください。

• $l+i \\le N$ である。
• 全ての $1 \\le k \\le l$ を満たす整数 $k$ について、 $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$ です。