当前没有测试数据。

F - 传送门和封闭城市

得分：500 分

问题描述

有 $N$ 个城市，编号为 $1$ 到 $N$。 还有一些单向传送门，可以将你传送到其他城市。 一个传送门能否直接将你从城市 $i$（$1\leq i\leq N$）传送到另一个城市，由长度为 $M$ 的字符串 $S_i$ 表示，其中字符串 $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$。

接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串 $S_i$。

输出

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

对于每个 $i$（$1\leq i\leq N-2$），第 $i$ 个整数应该是对于 $k=i+1$，所得到的答案。

样例

输入：

5 2
11
01
11
10
00

输出：

2 3 2

输入：

6 3
101
001
101
000
100
000

输出：

-1 3 3 -1