P6380 『MdOI R2』Mayuri

「万由里……怎么会？为什么你要……」 『我是灵力的结晶体，实施了封印，我当然会消失，不是吗？』 「封印？但是你和我……」 『第一次见面不能封印吗？笨蛋，我可是从大家的灵力里出生的，怎么可能讨厌你？从一出生，我就爱着你。』 「万由里……」 『虽然我竭力不让自己去想，但我一定是很羡慕大家……』 「等一下，万由里，不要消失……」 『但是我还是有一件能向大家炫耀的事，只有我和士道一样……』 「一样？」 『我已经不再是只为了消失而出生的生命。因为我遇见了你……已经足够了。』 「万由里……」 『谢谢你，士道。 』 

在离开这个世界前，万由里想要寻找属于她的 Lucky Number。 万由里会给出一个数 $a$，以及一个长度为 $b$ 的 01 串 $S$。 简单的说，她的 Lucky Number 是满足以下条件的**正整数** $n$： - $n$ 的位数为 $b$ 且不含前导 $0$。 - 若 $S$ 的第 $i$ 位为 $1$，则 $n$ 的前 $i$ 位组成的数是 $a$ 的倍数，否则 $n$ 的前 $i$ 位组成的数不是 $a$ 的倍数。 对于一个数，前 $i$ 位组成的数是指这个数前 $i$ 个数码依次拼接形成的数。例如 $312311$ 前 $3$ 位组成的数为 $312$，前 $5$ 位组成的数为 $31231$。 现在，请你帮助万由里计算一下，她的 Lucky Number 是多少。 由于满足条件的数可能会有多个，你需要输出**最小**的一个。若不存在，则请输出 `-1`。

输入数据由两行构成。 第一行两个整数 $a,b$，意义见题目描述。 第二行一个长度为 $b$ 的字符串 $S$。

一行，满足条件的**最小**的数 $n$。如果不存在满足条件的数，输出 `-1`。

【帮助与提示】 为方便选手测试代码，本题额外提供一组附加样例供选手使用。 [样例输入](https://www.luogu.com.cn/paste/5gnn8mg0) [样例输出](https://www.luogu.com.cn/paste/sgxjkbjd) ------ 【样例解释】 对于样例一，$10$ 是 $2$ 位数，且 $10$ 的前 $1$ 位组成的数 $1$ 不是 $2$ 的倍数，而前 $2$ 位组成的数 $10$ 是 $2$ 的倍数。由于 $10$ 已经是最小的两位数，故不存在比 $10$ 更小的满足条件的数。 对于样例二，我们需要构造一个 $1$ 位数，满足这个 $1$ 位数整除 $10$。显然，这样的数不存在。 --- 【数据范围】 **本题采用捆绑测试** | 子任务编号 | $a \leq$ | $b\le$ | 分值 | | ---------- | -------- | :------ | ------ | | Subtask 1 | $10$ | $ 1$ | $20$ | | Subtask 2 | $10 $ | $2$ | $20$ | | Subtask 3 | $10 $ | $ 6$ | $20$ | | Subtask 4 | $ 2$ | $ 18$ | $20$ | | Subtask 5 | $ 10$ | $ 10^5$ | $20$ | 对于全部数据，保证 $2\le a\le 10$，$1\le b\le 10^5$，$S$ 中只包含 `0` 和 `1`。