题目描述

高桥正在玩一个叫做“跑得快”的棋盘游戏。 棋盘上一共有 $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行，两个正整数$N,M$

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

输出

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

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

9 3
0001000100

1 3 2 3

样例说明

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

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

5 4
011110

-1

6 6
0101010

6

提示

• $1\ <\ =\ N\ <\ =\ 10^5$
• $1\ <\ =\ M\ <\ =\ 10^5$
• $|S|\ =\ N\ +\ 1$
• $S[0]\ =$ 0
• $S[N]\ =$ 0