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.
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.
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|).
1 3 6 10 15