Background

"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."

Problem Description

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.

Input Format

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 Format

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

2 2
01

10

10 1 
1

-1

6 6
110100

601210

Hint

【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 Sample Output

【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.

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