AT_abc213_f [ABC213F] Common Prefixes

[problemUrl]: https://atcoder.jp/contests/abc213/tasks/abc213_f $ 2 $ つの文字列 $ X,Y $ に対して、その**類似度** $ f(X,Y) $ を、$ X $ と $ Y $ を先頭から見て一致している文字数とします。 例えば `abc` と `axbc` の類似度は $ 1 $ 、`aaa` と `aaaa` の類似度は $ 3 $ です。 長さ $ N $ の文字列 $ S $ が与えられます。$ S $ の $ i $ 文字目以降からなる文字列を $ S_i $ とします。$ k=1,\ldots,N $ のそれぞれについて、$ f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N) $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

$ N $ 行出力せよ。 $ i $ 行目には $ k=i $ の問題の答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^6 $ - $ S $ は英小文字のみからなる長さ $ N $ の文字列 ### Sample Explanation 1 $ S_1,S_2,S_3 $ はそれぞれ `abb`, `bb`, `b` です。 - $ k=1 $ のとき $ f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3 $ - $ k=2 $ のとき $ f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3 $ - $ k=3 $ のとき $ f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2 $