Practice on Toph

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

Distinctness

Limits: 500ms, 256 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
zx
1
3

Author
  • raihatneloy's Avatar

    raihatneloy

    Raihat is a student of Jahangirnagar University. He loves playing video games, solving problems and spreading knowledge of sport programming. He rarely spends a day without solving a problem or playing a match in FIFA.
Discussion
Submit

Login to submit