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.text.DecimalFormat;
import java.util.*;
import java.io.*;



public class Main {
    private static int [] [] dist = new int[501][5001];

    public static void main(String[] args) throws Exception {
        IO io ;
        try {
            io = new IO("in.in", null);
        } catch (IOException e) {
            io = new IO(null, null);
        }
        int M = io.getNextInt();
        int S = io.getNextInt();
        int [] [] link = new int[M][S+1];
        int [] [] R = new int[M][S+1];

        for (int i = 0;i < M;i++)
            for (int j = 0;j <= S;j++)
                dist[i][j] = 1 << 29;
        Queue<node> q = new LinkedList<>();
        q.add(new node(0,S,0,0));
        dist[0][S] = 0;
        for (int t = 1;!q.isEmpty();) {
            node cur = q.poll();
            if (cur.d > dist[cur.r][cur.s]) continue;
            if (cur.r == 0 && cur.s == 0) break;
            for (int d = 0;d < 10 && d <= cur.s;d++) {
                int r = (cur.r * 10 + d)%M;
                int s = cur.s - d;
                int c = cur.d + 1;
                if (c < dist[r][s]) {
                    dist[r][s] = c;
                    link[r][s] = d;
                    R[r][s] = cur.r;
                    q.add(new node(r,s,c,t++));
                }
            }
        }
        int oo = 1 << 29;
        if (dist[0][0] == oo) io.println(-1);
        else {
            Stack<Integer> ST = new Stack<>();
            int r = 0,s = 0;
            while (r != 0 || s != S) {
                int d = link[r][s];
                ST.add(d);
                r = R[r][s];
                s += d;
            }
            while (!ST.isEmpty())
                io.print(ST.pop());
            io.println("");
        }
        io.close();
    }
    private static final int onebillion7 = 1000000007;
}


class node implements Comparable<node>{
    int r,s,d,t;
    public node(int r,int s,int d,int t) {
        this.r = r;
        this.s = s;
        this.d = d;
        this.t = t;
    }
    @Override
    public int compareTo(node o) {
        if (d == o.d) return t - o.t;
        return d - o.d;
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}