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 javax.management.Query;
import java.util.*;
import java.io.*;

public class A100187 {

    static ArrayList<Integer> getdigit(int id, int[] p, int s, int[] pp) {
        ArrayList<Integer> ans = new ArrayList<>();
        while (id != s) {
            ans.add(p[id]);
            id = pp[id];
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int d = sc.nextInt();
        int s = sc.nextInt();
        boolean[] vis = new boolean[d * (s + 1)];
        int[] parent = new int[d * (s + 1)];
        Arrays.fill(parent, -1);
        int[] edge = new int[d * (s + 1)];
        Queue<Integer> q = new LinkedList<>();
        vis[s] = true;
        ((LinkedList<Integer>) q).add(s);
        while (!q.isEmpty()) {
            int cur = q.poll();
            int dd = cur / (s + 1);
            int ss = cur - (dd * (s + 1));

//            System.err.println(getdigit(cur, edge, s, parent));
            for (int i = 0; i <= 9; i++) {
                int nxtd = (dd * 10 + i) % d;
                int nxsts = ss - i;
                if (nxsts < 0)
                    continue;
                int id = nxtd * (s + 1) + nxsts;
                if (!vis[id]) {
                    vis[id] = true;
                    parent[id] = cur;
                    edge[id] = i;
                    ((LinkedList<Integer>) q).add(id);
                }
            }
        }
        ArrayList<Integer> ans = new ArrayList<>();
        if (!vis[0]) {
            pw.println(-1);
        } else {
            int st = 0;
            while (st != s) {
                ans.add(edge[st]);
                st = parent[st];
            }
            Collections.reverse(ans);
            for (int x : ans)
                pw.print(x);
            pw.println();
        }
        pw.flush();
    }

    static class Scanner {
        BufferedReader br;
        StringTokenizer st;

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

        public Scanner(FileReader f) {
            br = new BufferedReader(f);
        }

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

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

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

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

        public int[] nextIntArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(next());
            }
            return arr;
        }

    }
}