For a string $s$ of length $n$, the function $z[i]$ is defined as the length of the longest common prefix (LCP) between $s$ and the suffix of $s$ starting at $i$ (i.e., $s[i, n-1]$). $z$ is called the Z-function of $s$. Specifically, $z[0] = 0$.

Given a string $s$, compute $z$.

Input

The input consists of a single line containing a string $S$ consisting only of lowercase letters.

Output

$z_0\, z_1\, z_2 \, \cdots \, z_{|S|-1}$

Examples

Input 1

abacababacbaacbabbabac

Output 1

0 0 1 0 3 0 4 0 1 0 0 1 1 0 0 2 0 0 4 0 1 0

Subtasks

For all data, $1 \leq |S| \leq 2 \cdot 10^6$.

• Subtask 1 (30 points): $|S| \leq 10^5$
• Subtask 2 (70 points): No additional constraints