- Time limit: 1.00 s
- Memory limit: 512 MB
You are given a bit string of length . Your task is to calculate for each between the number of non-empty substrings that contain exactly ones.
For example, if the string is 101, there are:
- 1 substring that contains 0 ones: 0
- 4 substrings that contain 1 one: 01, 1, 1, 10
- 1 substring that contains 2 ones: 101
- 0 substrings that contain 3 ones
Input
The only input line contains a binary string of length .
Output
Print values as specified above.
Constraints
Example
Input:
101
Output:
1 4 1 0