问题描述

有 $N$ 个城市，编号为城市 $1$，城市 $2$，……，城市 $N$。
还有一种单向传送器，可以将你传送到不同的城市。传送器是否可以直接从城市 $i$ $(1\leq i\leq N)$ 发送到另一个城市由长度为 $M$ 的字符串 $S_i$ 表示，该字符串由 0 和 1 组成。具体来说，对于 $1\leq j\leq N$，

• 如果 $1\leq j-i\leq M$，并且 $S_i$ 的第 $(j-i)$ 个字符是 1，则传送器可以直接将你从城市 $i$ 送到城市 $j$；
• 否则，它不能直接将你从城市 $i$ 送到城市 $j$。

解决以下问题，对于 $k=2,3,\ldots,N-1$：

你能通过反复使用传送器从城市 $1$ 到达城市 $N$ 而不经过城市 $k$ 吗？如果可以，请打印你需要使用传送器的最小次数；否则，打印 $-1$。

约束条件

• $3 \leq N \leq 10^5$
• $1\leq M\leq 10$
• $M<N$
• $S_i$ 是长度为 $M$ 的由 0 和 1 组成的字符串。
• 如果 $i+j>N$，则 $S_i$ 的第 $j$ 个字符是 0。
• $N$ 和 $M$ 是整数。

输入

输入以以下格式从标准输入给出：

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

输出

在一行中打印 $(N-2)$ 个用空格分隔的整数。第 $i$ 个 $(1\leq i\leq N-2)$ 整数应该是对于 $k=i+1$ 的问题的答案。

示例输入1

5 2
11
01
11
10
00

示例输出1

2 3 2

传送器可以将你从城市 $1$ 送到城市 $2$ 和 $3$； 传送器可以将你从城市 $2$ 送到城市 $4$； 传送器可以将你从城市 $3$ 送到城市 $4$ 和 $5$； 传送器可以将你从城市 $4$ 送到城市 $5$； 传送器无法将你从城市 $5$ 送到其他城市。

因此，有三条路径可以从城市 $1$ 到达城市 $5$：

• 路径 $1$：城市 $1$ $\\to$ 城市 $2$ $\\to$ 城市 $4$ $\\to$ 城市 $5$；
• 路径 $2$：城市 $1$ $\\to$ 城市 $3$ $\\to$ 城市 $4$ $\\to$ 城市 $5$；
• 路径 $3$：城市 $1$ $\\to$ 城市 $3$ $\\to$ 城市 $5$；

在这些路径中，

• 两条路径，路径 $2$ 和路径 $3$，都没有经过城市 $2$。其中，路径 $3$ 需要使用传送器的最小次数（两次）。
• 路径 $1$ 是唯一不经过城市 $3$ 的路径。需要使用传送器三次。
• 路径 $3$ 是唯一不经过城市 $4$ 的路径。需要使用传送器两次。

因此，应该打印 $2$、$3$ 和 $2$，用空格分隔。

示例输入2

6 3
101
001
101
000
100
000

示例输出2

-1 3 3 -1

从城市 $1$ 到达城市 $6$ 的唯一路径是城市 $1$ $\\to$ 城市 $2$ $\\to$ 城市 $5$ $\\to$ 城市 $6$。
对于 $k=2,5$，无法从城市 $1$ 到达城市 $6$ 而不经过城市 $k$。
对于 $k=3,4$，上述路径满足条件；需要使用传送器三次。

因此，应该打印 $-1$、$3$、$3$ 和 $-1$，用空格分隔。

请注意，传送器是单向的；传送器可以将你从城市 $3$ 送到城市 $4$，但不能从城市 $4$ 送到城市 $3$， 因此，以下路径无效：城市 $1$ $\\to$ 城市 $4$ $\\to$ 城市 $3$ $\\to$ 城市 $6$。