시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 2 2 2 100.000%

문제

For two strings $S$ and $P$, let the value $f (S, P)$ be the number of occurrences of $P$ in $S$. For example, $f$("ababa", "aba") = 2, and $f$("aaaaa", "aa") = 4.

For a string $S$, let the value $g (S)$ be the sum of squares of the occurrence counts in $S$ for all possible non-empty strings. More formally, $g (S) = \sum \big( f (S, P)^2 \big)$ for all possible non-empty strings $P$.

You have given a string of length $n$: $S = c_1 c_2 \ldots c_n$. Let $r_i = g (c_1 c_2 \ldots c_i)$. Calculate the values $r_i$ for all $i$ from $1$ to $n$.

입력

The first line contains the string $S$ which consists of lowercase English letters. The length of $S$ is between $1$ and $10^5$ letters, inclusive.

출력

Print $n$ lines. The $i$-th line must contain the integer $r_i$.

예제 입력 1

aaa

예제 출력 1

1
5
14

예제 입력 2

pqpq

예제 출력 2

1
3
8
16

예제 입력 3

stssts

예제 출력 3

1
3
8
16
25
41