Blocks of string#1309

Blocks of string

1 second

128 megabytes

Very easy

The block of a string $S$ at position $i$ is defined as the largest substring starting at position $i$ that 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 ∣ \leq 1 0^{6}$ |S| \le 10^6).

Output

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

Examples

Example 1

Loading

∣ S ∣ \leq 1 0^{6}