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 javafx.beans.binding.StringBinding;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

import static java.lang.Math.pow;
import static java.lang.Math.toIntExact;

public class E1066 {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader inp = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver1066D solver = new Solver1066D();
        solver.solve(inp, out);
        out.close();
    }

    static class InputReader {
        StringTokenizer tokenizer;
        InputStreamReader sReader;
        BufferedReader reader;

        InputReader(InputStream stream) {
            sReader = new InputStreamReader(stream);
            reader = new BufferedReader(sReader, 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

        public List<Integer> intLine(int size) {
            List<Integer> ls = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                ls.add(nextInt());
            }
            return ls;
        }

        int nextC() {
            try {
                return reader.read();
            } catch (IOException e) {
                return -1;
            }
        }

        public int[] intArr(int size) {
            int[] ls = new int[size];
            for (int i = 0; i < size; i++){
                ls[i] = nextInt();
            }
            return ls;
        }
    }

    static class Solver1066D {
        int d, reqS;
        public void solve(InputReader inp, PrintWriter out) {
            d = inp.nextInt();
            reqS = inp.nextInt();

            Queue<Tuple> pq = new LinkedList<>();
            pq.add(new Tuple(0, 0, new StringBuilder("")));
            boolean[][] visited = new boolean[5001][500]; // d%d= 0, sum(digits) =5000 =>visited[5000]
            while (!pq.isEmpty()){
                Tuple curr = pq.poll();
                if (curr.remainder == 0 && curr.sumD == reqS){
                    out.println(curr.value);
                    return;
                }
                for (int i = 0; i < 10; i++){
                    int sum = curr.sumD+i;
                    int remain = (curr.remainder*10 + i)%d;
                    if (sum <= reqS && !visited[sum][remain]){
                        visited[sum][remain] = true;
                        StringBuilder sb = new StringBuilder(curr.value);
                        pq.add(new Tuple(sum, remain, sb.append(i)));
                    }
                }
            }
            out.println(-1);
        }
    }
}


class Tuple{
    int sumD, remainder;
    StringBuilder value;
    public Tuple(int sumD, int remainder, StringBuilder value){
        this.sumD = sumD;
        this.remainder = remainder;
        this.value = value;
    }

    @Override
    public String toString() {
        return this.sumD +", " +this.remainder + ", "+this.value;
    }
}