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.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;

public class Task {

    public static void main(String[] args) throws IOException {

        new Task().go();
    }

    PrintWriter out;
    Reader in;
    BufferedReader br;

    Task() throws IOException {

        try {

            //br = new BufferedReader( new FileReader("input.txt") );
            in = new Reader("input.txt");
            out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) );
        }
        catch (Exception e) {

            //br = new BufferedReader( new InputStreamReader( System.in ) );
            in = new Reader();
            out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) );
        }
    }

    void go() throws IOException {

        int t = 1;
        while (t > 0) {
            solve();
            //out.println();
            t--;
        }

        out.flush();
        out.close();
    }

    int inf = 2000000000;
    int mod = 1000000007;
    double eps = 0.000000001;

    int n;
    int m;

    ArrayList<Integer>[] g;
    int[] a;

    void solve() throws IOException {

        int d = in.nextInt();
        int s = in.nextInt();

        Vertex[][] dp = new Vertex[d][5001];

        LinkedList<Vertex> q = new LinkedList<>();

        dp[0][0] = new Vertex(0, 0, 0, null, 0);
        q.add(dp[0][0]);

        while (!q.isEmpty()) {
            Vertex v = q.poll();

            for (int i = 0; i < 10; i++) {
                int m = (v.m * 10 + i) % d;
                int sm = v.s + i;

                if (sm <= s) {
                    if (dp[m][sm] == null) {
                        dp[m][sm] = new Vertex(i, m, sm, v, v.l + 1);
                        q.add(dp[m][sm]);
                    }
                }
            }
        }

        Vertex cur = dp[0][s];

        if (cur == null) {
            out.print(-1);
            return;
        }

        StringBuilder ans = new StringBuilder();

        while (cur.l != 0) {
            ans.append(cur.d);
            cur = cur.prev;
        }

        out.print(ans.reverse());

    }

    class Vertex {
        int d;
        int m;
        int s;
        int l;
        Vertex prev;

        Vertex(int d, int m, int s, Vertex prev, int l) {
            this.d = d;
            this.prev = prev;
            this.m = m;
            this.s = s;
            this.l = l;
        }

    }

    int gcd(int a, int b){
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    class Pair implements Comparable<Pair>{
        int a;
        int b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public int compareTo(Pair p) {
            if (a > p.a) return 1;
            if (a < p.a) return -1;
            if (b > p.b) return 1;
            if (b < p.b) return -1;
            return 0;
        }
    }

    class Item {

        int a;
        int b;
        int c;

        Item(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

    }

    class Reader {

        BufferedReader  br;
        StringTokenizer tok;

        Reader(String file) throws IOException {
            br = new BufferedReader( new FileReader(file) );
        }

        Reader() throws IOException {
            br = new BufferedReader( new InputStreamReader(System.in) );
        }

        String next() throws IOException {

            while (tok == null || !tok.hasMoreElements())
                tok = new StringTokenizer(br.readLine());
            return tok.nextToken();
        }

        int nextInt() throws NumberFormatException, IOException {
            return Integer.valueOf(next());
        }

        long nextLong() throws NumberFormatException, IOException {
            return Long.valueOf(next());
        }

        double nextDouble() throws NumberFormatException, IOException {
            return Double.valueOf(next());
        }


        String nextLine() throws IOException {
            return br.readLine();
        }

    }

}