ADASTRNG - 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

Added by:Morass
Date:2017-10-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Tunisian Collegiate Training Contest - Round #01

hide comments
2024-08-21 00:37:49
Finally, a suffix array problem that doesn't give you a TLE verdict
2022-09-03 23:46:46
looooooooooooooooooooooong looooooooooooooooooooooooong
2020-04-14 11:01:21
long long cost me a wa
2019-11-18 20:40:51
Nothing ;)

Last edit: 2019-11-18 20:50:48
2018-10-13 21:09:41
easy one go!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.