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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
int D, s, f[505][5005], d[2600005], r[2600005], la[2600005], wy[2600005], cnt;
vector<int> Q[2600005];
pair<int, int> P[2600005];
void out(int x) {
  if (d[x]) {
    out(la[x]);
    putchar(48 + wy[x]);
  }
}
int main() {
  scanf("%d%d", &D, &s);
  for (int i = 0; i < D; ++i) {
    for (int j = 0; j <= s; ++j) {
      f[i][j] = ++cnt;
    }
  }
  memset(d, -1, sizeof(d));
  d[1] = 0;
  Q[0].push_back(1);
  for (int _ = 0; Q[_].size(); ++_) {
    cnt = 0;
    for (int i = 0; i < Q[_].size(); ++i) {
      int k = Q[_][i];
      P[++cnt] = make_pair(r[la[k]] * 10 + wy[k], k);
    }
    Q[_].clear();
    sort(P + 1, P + cnt + 1);
    int k = 0;
    for (int i = 1; i <= cnt; ++i) {
      if (i == 1 || P[i].first != P[i - 1].first) ++k;
      r[P[i].second] = k;
    }
    for (int i = 1; i <= cnt; ++i) {
      int x = P[i].second, I, J;
      J = (x - 1) % (s + 1), I = (x - J) / (s + 1);
      vector<int> v, e;
      for (int k = 0; k < 10 && J + k <= s; ++k) {
        int f2 = f[(I * 10 + k) % D][J + k];
        v.push_back(f2);
        e.push_back(k);
      }
      for (int j = 0; j < v.size(); ++j) {
        int y = v[j];
        if (d[y] == -1) {
          d[y] = _ + 1;
          Q[_ + 1].push_back(y);
          la[y] = x;
          wy[y] = e[j];
        } else if (d[y] == _ + 1) {
          if (r[la[y]] * 10 + wy[y] > r[x] * 10 + e[j]) {
            la[y] = x;
            wy[y] = e[j];
          }
        }
      }
    }
  }
  int k = f[0][s];
  if (d[k] == -1) {
    puts("-1");
  } else {
    out(k);
    putchar('\n');
  }
  return 0;
}