F - 跑得快

得分：$600$ 分

问题描述

高桥正在玩一个叫做“跑得快”的棋盘游戏。

棋盘上一共有 $N + 1$ 个方格，编号从 $0$ 到 $N$。高桥从方格 $0$ 开始，他必须在方格 $N$ 停下来才能赢得比赛。

这个游戏使用一个有 $M$ 个数字的转盘，数字从 $1$ 到 $M$。每次高桥都要旋转转盘。如果当他在方格 $s$ 时出现数字 $x$，他就会移到方格 $s+x$。如果这使他超出方格 $N$，他就会输掉比赛。

此外，一些方格是“游戏结束方格”。如果他停在其中一个方格上，他也会输掉比赛。给定一个长度为 $N + 1$ 的字符串 $S$，表示哪些方格是游戏结束方格。对于每个 $i$ $(0 \leq i \leq N)$，如果 $S[i] = 1$，则方格 $i$ 是游戏结束方格，否则方格 $i$ 不是。

找到转盘中数字的序列，高桥可以在尽可能少的回合中赢得比赛。如果有多个这样的序列，找出字典序最小的一个。如果高桥不能赢得比赛，则打印 $-1$。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 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$。他不能在三回合或更少的回合内到达方格 $9$，而这是他在四回合内到达方格 $9$ 的字典序最小的序列。

样例输入2

5 4
011110

样例输出2

-1

高桥无法到达方格 $5$。

样例输入3

6 6
0101010

样例输出3

6