题目描述

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

この双六には $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$ を出力してください。

输入格式

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

$N$ $M$ $S$

输出格式

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

题目大意

ABC146F 双六

【题目描述】

高桥君在玩双六棋，棋盘格由用$0$到$N$编号的共$N+1$个格子构成。每一回合，高桥君会扔一个点数$1$到$M$的骰子。如果高桥君当前在第$i$格，骰子扔出$k$点，高桥君就前进到第$i+k$格。 如果此时$i+k > N$，高桥君立刻输掉。另外，棋盘上还有若干个“GameOver格”，如果高桥停在这些格子，也立刻输掉游戏。

假设高桥君可以自由控制骰子的点数，那么他从$0$号格子出发，到达$N$号格子，最短需要多少回合？输出用最短回合到达$N$格时，每回合骰子的点数组成的序列；如果无法到达$N$号格子，输出-1。

【输入格式】

第1行，两个正整数$N,M$

第2行，一个长为$N+1$的字符串$S$。$S_i=0$表示第$i$格是一个普通格子；$S_i=1$表示第$i$格是一个GameOver格。

【输出格式】

输出用最短回合到达$N$格时，每回合骰子的点数组成的序列，若有多种序列回合数都是最短，输出其中字典序最小的。

如果无法到达$N$号格子，输出-1。

【输入样例#1】

9 3
0001000100

【输出样例#1】

1 3 2 3

【样例#1说明】

按$1,3,2,3$的顺序扔出骰子的点数，高桥君会经过第$1,4,6$格最终到达第$9$格。

无法在$3$次以内到达第$9$格。$1,3,2,3$是所有$4$次到达第$9$格的点数序列中，字典序最小的。

【数据说明】

$1 \le N \le 10^5$

$1 \le M \le 10^5$

$S$长度为$N+1$，只由字符'0'和'1'组成，保证$S_0=0$，$S_N=0$。

9 3
0001000100

1 3 2 3

5 4
011110

-1

6 6
0101010

6

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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