Blocks of string

The Block of the string $S$ at position $i$ is the largest substring $S$ that starts at position $i$ and matches a prefix of $S$. The length of the block at position $0$ is considered to be zero.

Find the lengths of the blocks of string $S$ for all positions.

Input

One string $S(|S|\le 10^6)$.

Output

Print a single line containing the lengths of the blocks of string $S$ for all positions.

Examples