Limits 500ms, 512 MB

A substring of string S is another string S' which occurs in string S. For example: S = aaba and one of it's substring S' = ab, because S' occurs in S at the position 3. (1 indexed).

A prefix T of string S is a substring of string S which starts from the left most edge of the string.

Now you are given a string S. You have to find the number of distinct substrings in every prefix of S.
i.e: You need to consider a prefix as main substring. Then find number of distinct substring in it. Here you have to answer for all the prefixes.

Input

The only line in the input contains a string S. (1 ≤ |S| ≤ 100000). The string will contain only lowercase letters.

Here, |S| means the length of string S.

Output

You need to print |S| lines. i'th line of this section should contain the number of distinct substring in the prefix of length i (1 ≤ i ≤ |S|).

Samples

InputOutput
abcde
1
3
6
10
15
InputOutput
zx
1
3

Submit

Login to submit.

Contributors

Statistics

33% Solution Ratio
Matrix.codeEarliest, May '16
Kuddus.6068Fastest, 0.0s
nhdantLightest, 8.4 MB
omar24Shortest, 1017B
Toph uses cookies. By continuing you agree to our Cookie Policy.