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 <class U, class T>
void Max(U &first, T second) {
  if (first < second) first = second;
}
template <class U, class T>
void Min(U &first, T second) {
  if (first > second) first = second;
}
template <class T>
void add(int &a, T b) {
  a = (a + b) % 1000000007;
}
inline long long gcd(long long a, long long b) {
  return b == 0 ? a : gcd(b, a % b);
}
int pow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % 1000000007;
    a = 1LL * a * a % 1000000007;
    b >>= 1;
  }
  return ans;
}
int pow(int a, int b, int c) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = 1LL * ans * a % c;
    a = 1LL * a * a % c;
    b >>= 1;
  }
  return ans;
}
int dp[501][5001], g[501][5001];
vector<int> f[10][501];
map<pair<pair<int, int>, int>, int> h;
void ins(int i, int u, int v) {
  pair<pair<int, int>, int> e = {{u, v}, i};
  h[e] = 1;
}
bool check(int i, int u, int v) {
  pair<pair<int, int>, int> e = {{u, v}, i};
  return h.count(e);
}
int main() {
  int ca = 0, T, k, i, j, K, n, m = 0;
  int d, s;
  scanf("%d%d", &d, &s);
  memset(dp, -1, sizeof(dp));
  vector<int> ans;
  dp[0][0] = 0;
  int L = -1;
  queue<pair<int, int> > qu;
  qu.push({0, 0});
  while (!qu.empty()) {
    pair<int, int> e = qu.front();
    qu.pop();
    int w = dp[e.first][e.second] + 1;
    for (int first = w == 1 ? 1 : 0; first < 10; first++) {
      if (e.second + first > s) break;
      int second = (e.first * 10 + first) % d;
      int z = e.second + first;
      if (dp[second][z] == -1) {
        dp[second][z] = w;
        qu.push({second, z});
      }
    }
  }
  L = dp[0][s];
  if (L == -1) {
    puts("-1");
    return 0;
  }
  for (int i = 0; i < d; i++) {
    for (int j = 0; j < 10; j++) {
      f[j][(i * 10 + j) % d].push_back(i);
    }
  }
  set<pair<int, int> > a, b;
  a.insert({0, s});
  ins(L, 0, s);
  for (int i = L - 1; i >= 0; i--) {
    b.clear();
    for (auto &o : a) {
      int first = o.first, second = o.second;
      for (int k = 0; k < 10; k++) {
        if (k > second) break;
        int z = second - k;
        for (auto &u : f[k][first]) {
          if (dp[u][z] == i) {
            ins(i, u, z);
            b.insert({u, z});
          }
        }
      }
    }
    swap(a, b);
  }
  int first = 0, second = 0, cnt = 100;
  m = 0;
  while (!(first == 0 && second == s)) {
    int ok = 0;
    for (int i = m == 0 ? 1 : 0; i < 10; i++) {
      int u = (first * 10 + i) % d;
      int v = second + i;
      if (check(m + 1, u, v) && dp[u][v] == m + 1) {
        ans.push_back(i);
        first = u;
        second = v;
        ok = 1;
        m++;
        break;
      }
    }
    assert(ok);
  }
  for (auto &first : ans) printf("%d", first);
  puts("");
}