双六

题目描述

高桥君在玩双六（日本的一种棋盘游戏）。

这个双六有编号为 $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$。

样例

9 3
0001000100

1 3 2 3

按 $1$、$3$、$2$、$3$ 的顺序出点数，高桥君可以经过格子 $1$、$4$、$6$ 到达格子 $9$。高桥君不可能在 $3$ 手以内到达格子 $9$，而在 $4$ 手内到达格子 $9$ 的点数序列中，这是字典序最小的。

5 4
011110

-1

高桥君无法到达格子 $5$。

6 6
0101010

6

数据范围

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