对于两个字符串 $S$ 和 $P$，令 $f(S, P)$ 为 $P$ 在 $S$ 中出现的次数。例如，$f(\text{"ababa"}, \text{"aba"}) = 2$，且 $f(\text{"aaaaa"}, \text{"aa"}) = 4$。

对于一个字符串 $S$，令 $g(S)$ 为 $S$ 中所有可能的非空字符串出现次数的平方和。更正式地，$g(S) = \sum_{P} f(S, P)^2$，其中 $P$ 为所有可能的非空字符串。

给定一个长度为 $n$ 的字符串 $S = c_1c_2 \dots c_n$。令 $r_i = g(c_1c_2 \dots c_i)$。请计算所有 $i$ 从 $1$ 到 $n$ 的值 $r_i$。

输入格式

第一行包含字符串 $S$，由小写英文字母组成。字符串长度在 $1$ 到 $10^5$ 之间（含边界）。

输出格式

输出 $n$ 行。第 $i$ 行必须包含整数 $r_i$。

样例

样例输入 1

aaa

样例输出 1

1
5
14

样例输入 2

pqpq

样例输出 2

1
3
8
16

样例输入 3

stssts

样例输出 3

1
3
8
16
25
41