問題文

高橋君は双六で遊んでいます。

この双六には $0$ から $N$ までの番号がついた $N + 1$ 個のマスがあります。高橋君はマス $0$ からスタートし、ゴールするにはマス $N$ にちょうど止まらなければなりません。

この双六では、$1$ から $M$ までの $M$ 種類の目が出るルーレットを使います。各手番で、高橋君はルーレットを回して出た目の数だけ進みます。この結果マス $N$ を越えて進むことになる場合、ゲームオーバーとなります。

また、いくつかのマスは「ゲームオーバーマス」であり、それらのマスに止まってもゲームオーバーとなります。マスの情報は長さ $N + 1$ の文字列 $S$ で与えられます。各 $i$ $(0 \\leq i \\leq N)$ について、S\[i\] = 1 のときマス $i$ はゲームオーバーマスであり、S\[i\] = 0 のときマス $i$ はゲームオーバーマスではありません。

高橋君がゲームオーバーとならずに最短手数でゴールするときの出目を順に答えてください。そのような目の出方が複数存在するときは、そのうち出目の列が辞書順で最小であるものを出力してください。ゲームオーバーとならずにゴールすることが不可能である場合は、 $\-1$ を出力してください。

制約

• $1 ≤ N ≤ 10^5$
• $1 ≤ M ≤ 10^5$
• $|S| = N + 1$
• $S$ は0と1から成る
• S\[0\] = 0
• S\[N\] = 0

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $S$

出力

ゴールすることが可能である場合、そのような最短の出目の列のうち辞書順で最小のものを出力せよ。ゴールすることが不可能である場合、$\-1$ を出力せよ。

入力例 1

9 3
0001000100

出力例 1

1 3 2 3

$1$ , $3$ , $2$ , $3$ の順に目を出すと、高橋君はマス $1$ , $4$ , $6$ を経由してマス $9$ に到達することが出来ます。高橋君が $3$ 手以内にマス $9$ に到達することは不可能であり、また $4$ 手でマス $9$ に到達するような出目の列の中ではこれが辞書順で最小です。

入力例 2

5 4
011110

出力例 2

-1

高橋君はマス $5$ に到達することが出来ません。

入力例 3

6 6
0101010

出力例 3

6