Problem: You are given two positive integers d and s. Find minimal positive integer n which is divisible by d and has sum of digits equal to s.

Input

The first line contains two positive integers d and s (1 ≤ d ≤ 500, 1 ≤ s ≤ 5000) separated by space.

Output

Print the required number or -1 if it doesn't exist.

Examples

Input

13 50


Output

699998


Input

61 2


Output

1000000000000000000000000000001


Input

15 50


Output

-1

Solution (in JAVA):

Solution:
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int n, s;
        boolean[][] f;

        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        s = scanner.nextInt();
        f = new boolean[n][s + 1];

        int l = 0, r = 0;
        int[] remainder = new int[n * s + 1];
        int[] sum = new int[n * s + 1];
        int[] from = new int[n * s + 1];
        int[] num = new int[n * s + 1];
        
        sum[0] = 0;
        from[0] = -1;
        num[0] = -1;
        f[0][0] = true;
        int tempRemainder, tempSum, resultRemainder, resultSum;
        while (l <= r) {
            tempRemainder = remainder[l] * 10;
            tempSum = sum[l];
            for (int i = 0; i < 10; i++) {
                resultRemainder = (tempRemainder + i) % n;
                resultSum = tempSum + i;
                if (resultSum <= s && !f[resultRemainder][resultSum]) {
                    r++;
                    remainder[r] = resultRemainder;
                    sum[r] = resultSum;
                    from[r] = l;
                    num[r] = i;
                    f[resultRemainder][resultSum] = true;
                    if (resultRemainder == 0 && resultSum == s) {
                        int index = r;
                        StringBuilder builder = new StringBuilder();
                        while (index != 0) {
                            builder.append(num[index]);
                            index = from[index];
                        }
                        System.out.println(builder.reverse().toString());
                        System.exit(0);
                    }
                }
            }
            l++;
        }
        System.out.println(-1);
    }
}