配点 : $500$ 点

問題文

$N$ 個の都市があり、都市 $1$, 都市 $2$, $\ldots$, 都市 $N$ と番号づけられています。 いくつかの異なる都市の間は一方通行のテレポーターによって移動できます。 都市 $i$ $(1\leq i\leq N)$ からテレポーターによって直接移動できる都市は 0 と 1 からなる長さ $M$ の文字列 $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$ を出力せよ。

制約

• $3 \leq N \leq 10^5$
• $1\leq M\leq 10$
• $M
• $S_i$ は 0 と 1 のみからなる長さ $M$ の文字列
• $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$ に対する問題の答えを出力せよ。

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$

の $3$ つがあり、

• 都市 $2$ を通らない経路は経路 $2$, 経路 $3$ の $2$つであり、そのうちテレポーターの使用回数が最小となるのは経路 $3$ で、この時 $2$ 回使用する。
• 都市 $3$ を通らない経路は経路 $1$ のみであり、この時テレポーターは $3$ 回使用する。
• 都市 $4$ を通らない経路は経路 $3$ のみであり、この時テレポーターは $2$ 回使用する。

となります。よって、$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$ の場合には上の方法が条件をみたし、テレポーターを $3$ 回使用します。

よって、$-1,3,3,-1$ をこの順に空白区切りで出力します。

テレポーターは一方通行であるため、 都市 $3$ から都市 $4$ へはテレポーターによって移動できますが、 都市 $4$ から都市 $3$ へは移動できず、 都市 $1$ $\to$ 都市 $4$ $\to$ 都市 $3$ $\to$ 都市 $6$ のような移動はできない事に注意してください。