Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Distinctness

By raihatneloy · 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

Discussion

Statistics


31% Solution Ratio

Matrix.codeEarliest, May '16

aritra741Fastest, 0.0s

nhdantLightest, 8.4 MB

omar24Shortest, 1017B

Submit

Login to submit

Related Contests

ProgKriya May'16
  • Ended May '16
Toph uses cookies. By continuing you agree to our Cookie Policy.