题目描述

李华在玩一款游戏，游戏中玩家初始在 $1$ 号点，游戏目标是到达 $n$ 号点。

对于每一个点 $i$ ，都会有一个对应的长度为 $m$ 的字符串 $s_i$ ，$s_i$ 仅由 $0$ 或 $1$ 组成，假如 $s_i$ 的第 $j$ 个位置为 $1$ ，表示点 $i$ 和点 $i+j$ 之间有一条长度为 $1$ 的边（如果 $i+j>n$ ，则保证 $s_i$ 的第 $j$ 位为 $0$ ）。

李华想要请你帮他解决如下问题：

对于 $k=2,3,...,n-1$ , 李华是否从点 $1$ 出发在不经过点 $k$ 的情况下到达点 $n$ ，如果能够到达，输出需要经过的最短路径，否则输出 $-1$ .

输入格式

第 $1$ 行，两个数字 $n,m$，表示点的个数和每个字符串的长度.

接下来 $n$ 行，每行一个长度为 $m$ 的字符串 $s_i$ .

输出格式

输出 $n-2$ 个数表示每一个 $k$ 的答案.

样例输入

4 2
11
00
11
00

样例输出

2 -1

数据范围

对于 $30\%$ 的数据，满足 $3\le n \le 10^3$, $1 \le m \le 10$ , $m<n$

对于 $100\%$​ 的数据，满足 $3\le n \le 10^{5}$, $1 \le m \le 10$ , $m<n$