Ada and Substring
Ada the Ladybug was exchanging gifts with her friend. What a surprise - they gave her string. As they like her very much, they brought her a very long string. The goodness of the string is the number of distinct substrings.
As you might already know, each letter has different value so Ada wants to know the number of distinct substrings beginning with each letter.
Input
The first and the only line line of each test-case will contain a string (formed by lowercase English letters) 1 ≤ |s| ≤ 3*105.
Output
For each test-case, print 26 integers, the number of distinct substrings beginning on given letter.
Example Input
aaa
Example Output
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Example Input
abc
Example Output
3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Example Input
aabbaa
Example Output
10 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Example Input
acbabca
Example Output
10 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Example Input
gdhgaghjdsahgdahjklflklkfsa
Example Output
50 0 0 57 0 10 84 69 0 30 17 18 0 0 0 0 0 0 18 0 0 0 0 0 0 0
Example Input
abababababbaaabbabbabababa
Example Output
130 123 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Example Input
aadsdadfafdfafdfsdfaf
Example Output
71 0 0 59 0 40 0 0 0 0 0 0 0 0 0 0 0 0 21 0 0 0 0 0 0 0