题目描述

Takahashi is playing a board game called Sugoroku.

On the board, there are $N + 1$ squares numbered $0$ to $N$. Takahashi starts at Square $0$, and he has to stop exactly at Square $N$ to win the game.

The game uses a roulette with the $M$ numbers from $1$ to $M$. In each turn, Takahashi spins the roulette. If the number $x$ comes up when he is at Square $s$, he moves to Square $s+x$. If this makes him go beyond Square $N$, he loses the game.

Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string $S$ of length $N + 1$, representing which squares are Game Over Squares. For each $i$ $(0 \leq i \leq N)$, Square $i$ is a Game Over Square if $S[i] = 1$ and not if $S[i] = 0$.

Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print $-1$.

高桥正在玩一款名为 "Sugoroku "的棋盘游戏。

棋盘上有 $N + 1$ 个方格，编号为 $0$ 至 $N$ 。高桥从第 $0$ 个方格开始下棋，他必须正好停在第 $N$ 个方格上才能获胜。

游戏使用的轮盘上有从 $1$ 到 $M$ 的 $M$ 个数字。每一轮，高桥都会转动轮盘。如果数字 $x$ 出现在他所在的方格 $s$ ，他就会移动到方格 $s+x$ 。如果这使得他移动到了 $N$ 方格之外，他就输掉了游戏。

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

找出轮盘中出现的数字序列，其中高桥可以在尽可能少的回合数内赢得游戏。如果有多个这样的序列，请找出词典上最小的序列。如果高桥不能赢得游戏，则打印 $-1$ 。

输入格式

输入内容按以下格式标准输入：

$N$ $M$
$S$

输出格式

如果高桥能赢得游戏，请打印轮盘中出现的高桥能赢得游戏的最短数字序列中按词序排列的最小序列，中间留空格。

如果高桥不能赢得游戏，则打印 $-1$ 。

样例 #1

样例输入 #1

9 3
0001000100

样例输出 #1

1 3 2 3

样例 #2

样例输入 #2

5 4
011110

样例输出 #2

-1

样例 #3

样例输入 #3

6 6
0101010

样例输出 #3

6

说明

数据规模与约定

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $|S| = N + 1$
• $S$ 由 0 和 1 组成。
• $S[0] =$ 0
• $S[N] =$ 0

样例 $1$ 解释

如果数字 $1$ ， $3$ ， $2$ ， $3$ 按照这个顺序出现，高桥可以通过方格 $1$ ， $4$ 和 $6$ 到达方格 $9$ 。他无法在三个或更少的回合内到达方格 $9$ ，而这是他在四个回合内到达方格 $9$ 的词典最小序列。

样例 $2$ 解释

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