You are given a string s of lowercase English letters. Cut it into contiguous, non-overlapping blocks so that each distinct letter appears in at most one block (all copies of a letter must lie in the same block). Among all such partitions, produce the one with the maximum number of blocks — this partition is unique.
Output the sizes of the blocks, in left-to-right order.
Input format
Line 1: the string s (only lowercase letters a-z, no spaces).
Output format
One line: the block sizes, space-separated, in order from the start of the string. The sizes sum to the length of s.
Constraints
- 1 <= length of s <= 100000
sconsists only of lowercase English letters.