传送门与封锁

题目描述

有 $N$ 个城市,编号为城市 $1$、城市 $2$、……、城市 $N$。

还有一些单向传送门,可以将你送到不同的城市。 从城市 $i$ $(1\leq i\leq N)$ 是否能直接传送到其他城市,由长度为 $M$ 的、由 0 和 1 组成的字符串 $S_i$ 表示。具体地,对于 $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$,解决以下问题:

能否通过反复使用传送门,在不经过城市 $k$ 的情况下从城市 $1$ 到达城市 $N$? 如果能够到达,输出需要使用传送门的最少次数;否则输出 $-1$。

输入格式

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

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

输出格式

在一行中输出 $N-2$ 个用空格分隔的整数。

第 $i$ 个整数 $(1\leq i\leq N-2)$ 应为 $k=i+1$ 时问题的答案。

样例

5 2
11
01
11
10
00

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$ 的路径有路径 2 和路径 3 两条。其中,路径 3 使用传送门的次数最少(两次)。

不经过城市 $3$ 的路径只有路径 1。它需要使用三次传送门。

不经过城市 $4$ 的路径只有路径 3。它需要使用两次传送门。

因此,应输出用空格分隔的 $2$、$3$、$2$。

6 3
101
001
101
000
100
000

-1 3 3 -1

从城市 $1$ 到城市 $6$ 的唯一路径是城市 $1$ $\to$ 城市 $2$ $\to$ 城市 $5$ $\to$ 城市 $6$。

对于 $k=2,5$,不经过城市 $k$ 时无法从城市 $1$ 到达城市 $6$。

对于 $k=3,4$,上述路径满足条件;它需要使用三次传送门。

因此,应输出用空格分隔的 $-1$、$3$、$3$、$-1$。

注意传送门是单向的; 传送门可以从城市 $3$ 送到城市 $4$, 但不能从城市 $4$ 送到城市 $3$。

因此,例如以下路径是无效的: 城市 $1$ $\to$ 城市 $4$ $\to$ 城市 $3$ $\to$ 城市 $6$。

数据范围

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