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.

\n

As you might already know, each letter has different value so Ada wants to know the number of distinct substrings begining with each letter.

\n

Input

\n

The first and the only line line of each test-case will contain a string (formed by lowercase english letters) 1 ≤ |s| ≤ 3*10⁵.

\n

Output

\n

For each test-case, print 26 integers, the number of distinct substrings beginning on given letter.

\n

Example Input

\n

aaa\n

\n

Example Output

\n

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\n

\n

Example Input

\n

abc\n

\n

Example Output

\n

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\n

\n

Example Input

\n

aabbaa\n

\n

Example Output

\n

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\n

\n

Example Input

\n

acbabca\n

\n

Example Output

\n

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\n

\n

Example Input

\n

gdhgaghjdsahgdahjklflklkfsa\n

\n

Example Output

\n

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\n

\n

Example Input

\n

abababababbaaabbabbabababa\n

\n

Example Output

\n

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\n

\n

Example Input

\n

aadsdadfafdfafdfsdfaf\n

\n

Example Output

\n

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\n

统计

递交统计

Ada and Substring

信息

状态

开发

支持

还没有账户？

登录