You are given a string $s$ and your task is to calculate the Z-array for the string. The Z-Array for a string is an array that, for each position $i$, stores the length of the longest substring starting from $i$ that matches a prefix of the string.

Input

The input consists of a single line containing a string $s$, consisting of lowercase English letters.

Output

Output a single line containing $|s|$ integers, the values of $Z_1, Z_2, Z_3, \dots, Z_{|s|}$.

Constraints

• $1 \leq |s| \leq 10^6$

Example

Input:

aabaaab

Output:

7 1 0 2 3 1 0