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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct node {
  int mod;
  int bitSum;
  string str;
  node() = default;
  node(const int& mod, const int& bit, const string& str)
      : mod(mod), bitSum(bit), str(str) {}
};
bool Vis[501][5001]{false};
string BFS(int p, int x) {
  queue<node> Q;
  Q.push(node(0, 0, ""));
  Vis[0][0] = true;
  while (!Q.empty()) {
    node Cur = Q.front();
    Q.pop();
    if (Cur.bitSum <= x) {
      if (Cur.mod == 0 && Cur.bitSum == x) {
        return Cur.str;
      }
      for (int Digit = 0; Digit < 10; ++Digit) {
        int Remainder = (Cur.mod * 10 + Digit) % p;
        int BitN = Cur.bitSum + Digit;
        if (Vis[Remainder][BitN] == false) {
          Vis[Remainder][BitN] = true;
          Q.push(
              node(Remainder, BitN, Cur.str + static_cast<char>(Digit + '0')));
        }
      }
    }
  }
  return "-1";
}
int main() {
  int p, x;
  cin >> p >> x;
  cout << BFS(p, x) << endl;
  return 0;
}