P6380 "MdOI R2" Mayuri

"Mayuri... how could this be? Why are you..." "I am the crystallization of spiritual power. After carrying out the seal, of course I will disappear, right?" "A seal? But you and I..." "Can't I be sealed even at our first meeting? Idiot. I was born from everyone's spiritual power, so how could I hate you? From the moment I was born, I loved you." "Mayuri..." "Even though I try my best not to think about it, I must be very jealous of everyone..." "Wait, Mayuri, don't disappear..." "But I still have one thing I can brag about to everyone. Only I am the same as Shido..." "The same?" "I am no longer a life born only to disappear. Because I met you... that is enough." "Mayuri..." "Thank you, Shido." 

Before leaving this world, Mayuri wants to find the Lucky Number that belongs to her. Mayuri will give a number $a$ and a binary string $S$ of length $b$. Simply put, her Lucky Number is a **positive integer** $n$ that satisfies the following conditions: - The number of digits of $n$ is $b$, and it has no leading $0$. - If the $i$-th character of $S$ is $1$, then the number formed by the first $i$ digits of $n$ is a multiple of $a$; otherwise, the number formed by the first $i$ digits of $n$ is not a multiple of $a$. For a number, the number formed by its first $i$ digits means the number obtained by concatenating the first $i$ digits in order. For example, for $312311$, the number formed by its first $3$ digits is $312$, and the number formed by its first $5$ digits is $31231$. Now, please help Mayuri compute her Lucky Number. Since there may be multiple numbers that satisfy the conditions, you need to output the **smallest** one. If it does not exist, output `-1`.

The input consists of two lines. The first line contains two integers $a, b$, with meanings as described in the statement. The second line contains a string $S$ of length $b$.

Output one line containing the **smallest** number $n$ that satisfies the conditions. If no such number exists, output `-1`.

【Help and Hints】 To make it easier for contestants to test their code, this problem additionally provides an extra set of sample cases for contestants to use. [Sample Input](https://www.luogu.com.cn/paste/5gnn8mg0) [Sample Output](https://www.luogu.com.cn/paste/sgxjkbjd) ------ 【Sample Explanation】 For sample 1, $10$ is a $2$-digit number, and the number formed by the first $1$ digit of $10$ is $1$, which is not a multiple of $2$, while the number formed by the first $2$ digits of $10$ is $10$, which is a multiple of $2$. Since $10$ is already the smallest two-digit number, there is no smaller number than $10$ that satisfies the conditions. For sample 2, we need to construct a $1$-digit number that is divisible by $10$. Obviously, such a number does not exist. --- 【Constraints】 **This problem uses bundled tests.** | Subtask ID | $a \leq$ | $b \leq$ | Score | | ---------- | -------- | -------- | ----- | | 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$ | For all testdata, it is guaranteed that $2 \le a \le 10$, $1 \le b \le 10^5$, and $S$ contains only `0` and `1`. Translated by ChatGPT 5