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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.Vector;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Queue;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AFindANumber solver = new AFindANumber();
        solver.solve(1, in, out);
        out.close();
    }

    static class AFindANumber {
        int d;
        int s;
        int INF = (int) 1e9;

        Stack<Integer> dijkstra() {
            int[][] dist = new int[d][s + 1];
            for (int[] x : dist)
                Arrays.fill(x, INF);
            Queue<Edge> pq = new LinkedList<>();
            dist[0][0] = 0;
            int[][][] parent = new int[d][s + 1][];
            pq.add(new Edge(0, 0));                        //may add more in case of MSSP (Mult-Source)
            int[][] digit = new int[d][s + 1];
            while (!pq.isEmpty()) {
                Edge cur = pq.remove();
                int start = cur.sum == 0 ? 1 : 0;
                for (int i = start; i <= 9; i++) {
                    int nextMod = (cur.mod * 10 + i) % d;
                    int nextsum = cur.sum + i;
                    if (nextsum <= s) {
                        Edge temp = new Edge(nextsum, nextMod);
                        if (dist[nextMod][nextsum] > dist[cur.mod][cur.sum] + 1) {
                            dist[nextMod][nextsum] = dist[cur.mod][cur.sum] + 1;
                            parent[nextMod][nextsum] = new int[]{cur.mod, cur.sum};
                            digit[nextMod][nextsum] = i;
                            pq.add(temp);
                        }
                    }
                }
            }
            int mod = 0;
            int sum = s;
            Stack<Integer> st = new Stack<>();
            if (dist[mod][sum] < INF) {
                while (parent[mod][sum] != null) {
                    st.add(digit[mod][sum]);
                    int[] temp = parent[mod][sum];
                    sum = temp[1];
                    mod = temp[0];
                }
            } else
                st.add(-1);
            return st;
        }

        public void readInput(Scanner sc) {
            d = sc.nextInt();
            s = sc.nextInt();
        }

        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            int q = 1;
            while (q-- > 0) {
                readInput(sc);
                Stack<Integer> st = dijkstra();
                while (!st.isEmpty())
                    pw.print(st.pop());
            }
        }

        class Edge {
            int sum;
            int mod;

            Edge(int a, int b) {
                sum = a;
                mod = b;
            }

            public String toString() {
                return "Edge{" +
                        "sum=" + sum +
                        ", mod=" + mod +
                        ", s='" + s + '\'' +
                        '}';
            }

        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}