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