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.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 * Created by Julia on 01.04.2017.
 */
public class SolverA {

    public static void main(String[] args) throws IOException {
        new SolverA().run();
    }

    StringTokenizer stok;
    BufferedReader br;
    PrintWriter pw;

    String nextToken() throws IOException {
        while (stok == null || !stok.hasMoreTokens()) {
            stok = new StringTokenizer(br.readLine());
        }
        return stok.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    void run() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new OutputStreamWriter(System.out));
//        br = new BufferedReader(new FileReader("input.txt"));
//        pw = new PrintWriter("output.txt");
        solve();
        pw.close();
    }

    class Num {
        byte digit;
        Num prev;

        public Num(byte digit, Num prev) {
            this.digit = digit;
            this.prev = prev;
        }
    }

    class Node {
        Num num;
        int sum;
        int rem;

        public Node(Num num, int sum, int rem) {
            this.num = num;
            this.sum = sum;
            this.rem = rem;
        }
    }

    Num zero = new Num((byte)0, null);

    private void solve() throws IOException {
        int mod = nextInt();
        int sum = nextInt();
        Node node = new Node(zero, 0, 0);
        Queue<Node> que = new LinkedList<>();
        que.add(node);
        boolean[][] found = new boolean[mod][sum + 1];
        found[0][0] = true;
        while (!que.isEmpty()) {
            Node cur = que.poll();
            byte mindig = 0;
            if (cur.sum == 0) {
                mindig = 1;
            }
            for (byte i=mindig; i<10; i++) {
                int nsum = cur.sum + i;
                int nrem = (cur.rem * 10 + i) % mod;
                Num nnum = new Num(i, cur.num);
                Node next = new Node(nnum, nsum, nrem);
                if (nsum <= sum && !found[nrem][nsum]) {
                    found[nrem][nsum] = true;
                    que.add(next);
                }
                if (nsum == sum && nrem == 0) {
                    Num num = next.num;
                    Stack<Byte> stack = new Stack<>();
                    while (num.prev != null) {
                        stack.push(num.digit);
                        num = num.prev;
                    }
                    while (!stack.isEmpty()) {
                        pw.print(stack.pop());
                    }
                    pw.println();
                    return;
                }
            }
        }
        pw.println(-1);
    }
}