長年ゲームを開催し、Bessie が何度も 1 位になるのを見て、Farmer John は偶然ではないと気付きました。Bessie の DNA には勝利が組み込まれているに違いないと考え、この「勝利」の遺伝子を探そうとします。

彼は「勝利」の遺伝子候補を見つける手順を考えました。Bessie のゲノムは長さ $N$ の文字列 $S$ で、$1 \leq N \leq 3000$ です。$1 \leq L \leq K \leq N$ を満たす組 $(K,L)$ を選びます。これは長さ $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

注記

このテストケースの出力の 3 行目は 5 です。3 つの「勝利」の遺伝子候補を与える $K$ と $L$ の組がちょうど 5 つあるためです。候補は次のとおりです（$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