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;
template <typename T>
T sqr(T x) {
  return x * x;
}
inline unsigned long long bit(int num) { return 1ull << num; }
const int DS = 10;
const int MAXK = 502;
const int MAXS = 5002;
const int MAXLEN = MAXK * MAXS + 5;
struct DpNode {
  operator bool() const { return digit != 0; }
  void setParent(pair<int, int> p, int pos, int d) {
    parent = p;
    position = pos;
    digit = d;
  }
  int digit;
  int position;
  pair<int, int> parent;
  vector<bool> tries;
  int tc;
  bool setTry(int d) {
    if (tries[d]) return false;
    tries[d] = true;
    ++tc;
    return tc == 9;
  }
  DpNode() : digit(digit), tc(0) { tries.assign(10, 0); }
};
DpNode dp[MAXK][MAXS];
void PrintAns(pair<int, int> v) {
  string s;
  {
    auto start = dp[v.first][v.second];
    s.assign(start.position + 1, '0');
  }
  while (true) {
    auto& dpr = dp[v.first][v.second];
    if (dpr.digit == -1) break;
    s[dpr.position] = '0' + dpr.digit;
    v = dpr.parent;
  }
  reverse((s).begin(), (s).end());
  cout << s << endl;
}
int main() {
  int k, s;
  cin >> k >> s;
  set<pair<int, int> > qs;
  qs.insert(pair<int, int>(0, 0));
  dp[0][0].digit = -1;
  int ten = 1 % k;
  auto t = std::chrono::system_clock::now();
  for (int pos = 0; pos < MAXLEN; ++pos) {
    vector<pair<int, int> > q(qs.begin(), qs.end());
    for (int d = 1; d < DS; ++d) {
      for (auto v : q) {
        pair<int, int> to((v.first + ten * d) % k, v.second + d);
        if (to.second > s) continue;
        if (!dp[to.first][to.second]) {
          dp[to.first][to.second].setParent(v, pos, d);
          qs.insert(to);
        } else {
          if (dp[v.first][v.second].setTry(d)) {
            qs.erase(v);
          }
        }
      }
    }
    if (dp[0][s]) {
      PrintAns(pair<int, int>(0, s));
      return 0;
    }
    ten *= 10;
    ten %= k;
    auto t1 = std::chrono::system_clock::now();
    if (t1 - t > std::chrono::milliseconds(2750)) {
      cerr << pos << endl;
      break;
    }
  }
  cout << -1 << endl;
  return 0;
}