### Problem Statement

There are $N$ cities numbered city $1$, city $2$, $\ldots$, and city $N$.  
There are also one-way teleporters that send you to different cities. Whether a teleporter can send you directly from city $i$ $(1\leq i\leq N)$ to another is represented by a length-$M$ string $S_i$ consisting of `0` and `1`. Specifically, for $1\leq j\leq N$,

-   if $1\leq j-i\leq M$ and the $(j-i)$-th character of $S_i$ is `1`, then a teleporter can send you directly from city $i$ to city $j$;
-   otherwise, it cannot send you directly from city $i$ to city $j$.

Solve the following problem for $k=2,3,\ldots, N-1$:

> Can you travel from city $1$ to city $N$ without visiting city $k$ by repeatedly using a teleporter? If you can, print the minimum number of times you need to use a teleporter; otherwise, print $-1$.

### Input

The input is given from Standard Input in the following format:

```
$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$
```

### Output

Print $(N-2)$ integers, separated by spaces, in a single line. The $i$-th $(1\leq i\leq N-2)$ integer should be the answer to the problem for $k=i+1$.

### Constraints

-   $3 \leq N \leq 10^5$
-   $1\leq M\leq 10$
-   $M<N$
-   $S_i$ is a string of length $M$ consisting of `0` and `1`.
-   If $i+j>N$, then the $j$-th character of $S_i$ is `0`.
-   $N$ and $M$ are integers.

2 3 2

A teleporter sends you

• from city 1 to cities 2 and 3;
• from city 2 to city 4;
• from city 3 to cities 4 and 5;
• from city 4 to city 5; and
• from city 5 to nowhere.

Therefore, there are three paths to travel from city 1 to city 5:

• path 1 : city 1 → city 2 → city 4 → city 5;
• path 2 : city 1 → city 3 → city 4 → city 5; and
• path 3 : city 1 → city 3 → city 5.

Among these paths,

• two paths, path 2 and path 3, do not visit city 2. Among them, path 3 requires the minimum number of teleporter uses (twice).
• Path 1 is the only path without city 3. It requires using a teleporter three times.
• Path 3 is the only path without city 4. It requires using a teleporter twice.

Thus, 2, 3, and 2, separated by spaces, should be printed.

-1 3 3 -1

The only path from city 1 to city 6 is city 1 → city 2 → city 5 → city 6.
For k=2,5, there is no way to travel from city 1 to city 6 without visiting city k.
For k=3,4, the path above satisfies the condition; it requires using a teleporter three times.
Thus, -1, 3, 3, and -1, separated by spaces, should be printed.
Note that a teleporter is one-way; a teleporter can send you from city 3 to city 4, but not from city 4 to city 3,
so the following path, for example, is invalid: city 1 → city 4 → city 3 → city 6.