题面翻译

对于两个字符串 $X,Y$，定义 $f(X,Y)$ 为 $X$ 和 $Y$ 的最长公共前缀长度。现给定一个长为 $n$ 的字符串 $S$，定义 $S_i$ 表示 $S$ 的从第 $i$ 个字符开始的后缀（包含第 $i$ 个字符），你需要对于所有的 $1\le k\le n$ 求出 $\sum\limits_{i=1}^nf(S_k,S_i)$。

样例 #1

样例输入 #1

3
abb

样例输出 #1

3
3
2

样例 #2

样例输入 #2

11
mississippi

样例输出 #2

11
16
14
12
13
11
9
7
4
3
4

提示

制約

• $1\ \leq\ N\ \leq\ 10^6$

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$