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.
The string S (|S| ≤ 10^6
).
Print in one line the block lengths of a string S for all positions, separated with a space.