题目描述

给定两个字符串 $X$ 和 $Y$，它们的相似度 $f(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)$。

约束条件

• $1 \\leq N \\leq 10^6$
• $S$ 是长度为 $N$ 的由小写英文字母组成的字符串。

输入

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

$N$ $S$

输出

打印 $N$ 行。

第 $i$ 行应该包含 $k=i$ 时的答案。

示例输入 1

3
abb

示例输出 1

3
3
2

$S_1$ 是 abb，$S_2$ 是 bb，$S_3$ 是 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$。

示例输入 2

11
mississippi

示例输出 2

11
16
14
12
13
11
9
7
4
3
4