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;
const int INFL = (int)1e9;
const long long int INFLL = (long long int)1e18;
const double INFD = numeric_limits<double>::infinity();
const double PI = 3.14159265358979323846;
bool nearlyeq(double x, double y) { return abs(x - y) < 1e-9; }
bool inrange(int x, int t) { return x >= 0 && x < t; }
long long int rndf(double x) {
  return (long long int)(x + (x >= 0 ? 0.5 : -0.5));
}
long long int floorsqrt(double x) {
  long long int m = (long long int)sqrt(x);
  return m + (m * m <= (long long int)(x) ? 0 : -1);
}
long long int ceilsqrt(double x) {
  long long int m = (long long int)sqrt(x);
  return m + ((long long int)x <= m * m ? 0 : 1);
}
long long int rnddiv(long long int a, long long int b) {
  return (a / b + (a % b * 2 >= b ? 1 : 0));
}
long long int ceildiv(long long int a, long long int b) {
  return (a / b + (a % b == 0 ? 0 : 1));
}
long long int gcd(long long int m, long long int n) {
  if (n == 0)
    return m;
  else
    return gcd(n, m % n);
}
struct val_t {
  int from_i, from_j;
  int x;
  bool done;
};
int main() {
  int d, s;
  cin >> d >> s;
  vector<vector<val_t>> table(d, vector<val_t>(s + 1, {-1, -1, -1, false}));
  queue<pair<int, int>> que;
  table[0][0] = {0, 0, 0, false};
  que.push({0, 0});
  while (que.size()) {
    pair<int, int> focus = que.front();
    que.pop();
    if (table[focus.first][focus.second].done) continue;
    table[focus.first][focus.second].done = true;
    for (int k = 0; k < (int)10; k++) {
      int i = (focus.first * 10 + k) % d;
      int j = focus.second + k;
      if (j <= s && table[i][j].x == -1) {
        table[i][j] = {focus.first, focus.second, k};
        que.push({i, j});
      }
    }
  }
  if (table[0][s].x == -1) {
    cout << -1 << endl;
  } else {
    string ans;
    int i = 0, j = s;
    while (!(i == 0 && j == 0)) {
      ans += '0' + table[i][j].x;
      int buf_i = i;
      int buf_j = j;
      i = table[buf_i][buf_j].from_i;
      j = table[buf_i][buf_j].from_j;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
  }
}