The Block of a string S at position i is the largest substring S which starts at position i and matches with the prefix S. The length of the block started at position 0 is assumed to be zero.

Find the block lengths of a string S for all positions.

Input

The string S (|S| ≤ 106).

Output

Print in one line the block lengths of a string S for all positions, separated with a space.