Given a string $S$, for each $i \in [1, n]$, define $\pi_i$ as the length of the longest border of $S[:i]$. Compute the array $\pi$.

Input

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

Output

Output a single line containing $|S|$ integers, representing $\pi_1, \pi_2, \dots, \pi_{|S|}$.

Constraints

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

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

Examples

Input 1

abcababcababcbacbabc

Output 1

0 0 0 1 2 1 2 3 4 5 6 7 8 0 1 0 0 1 2 3

Input 2

See provided files.

Output 2

See provided files.

Input 3

See provided files.

Output 3

See provided files.