Division

Time limit2sMemory limit512 MB

Summary

Change the fewest digits of n so the resulting number has no leading zeros and is divisible by m, or report -1.

Level: Medium7 of 10
Topics: Dynamic programming, Math, Greedy, Brute force
Solved: No attempts yet

Problem

Today Lesha learned long division at school. For homework he was asked to compute the quotient of two large numbers: $n$ and $m$ . Lesha already tried to solve the example, but unexpectedly realized that $n$ is not divisible by $m$ . He is sure that the teacher gave an example whose result has no remainder, so he assumed he made a mistake when copying the example from the board.

Now he wants to change a few digits in the number $n$ so that it becomes divisible by $m$ . At the same time, Lesha wants the new number to differ from the one he wrote down in the minimum number of positions.

The numbers Lesha wrote down have no leading zeros, and he is sure that the numbers written on the board also had no leading zeros, so the new number must not have them either. The number 0 itself is allowed.

Help Lesha.

Input

The single line of the input file contains two integers $n$ , $m$ ( $0 \le n \le 10^{11}$ , $1 \le m \le 10^{11}$ ).

Output

Print a single integer on the single line of the output file: the result of changing the minimum number of digits in $n$ so that the resulting number has no leading zeros and is divisible by $m$ .

If there are several answers, you may print any of them. If no answer exists, print $-1$ .

Examples4

Example 1
Input
```
123 10
```
Expected output
```
120
```
Example 2
Input
```
123 141
```
Expected output
```
423
```
Example 3
Input
```
9 123
```
Expected output
```
0
```
Example 4
Input
```
12 123
```
Expected output
```
-1
```