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 inf = 1 << 30;
const long long linf = 1LL << 62;
const int MAX = 510000;
const int V = 100005;
long long dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};
long long dx[8] = {0, 1, 0, -1, 1, -1, -1, 1};
const double pi = acos(-1);
template <typename T1, typename T2>
inline void chmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
template <typename T1, typename T2>
inline void print2(T1 a, T2 b) {
  cout << a << " " << b << endl;
}
const int mod = 1e9 + 7;
long long modpow(long long x, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}
int main() {
  long long d, s;
  cin >> d >> s;
  queue<pair<long long, long long> > q;
  q.emplace(0, 0);
  vector<vector<long long> > table(d, vector<long long>(5005, 0));
  table[0][0] = 1;
  vector<vector<pair<long long, long long> > > now(
      d, vector<pair<long long, long long> >(5005, make_pair(-1, -1)));
  while (!q.empty()) {
    pair<long long, long long> p = q.front();
    q.pop();
    for (long long i = 0; i < (10); i++) {
      long long a = (p.first * 10 + i) % d;
      long long b = p.second + i;
      if (b > s) break;
      if (table[a][b]) continue;
      table[a][b] = 1;
      now[a][b].first = i;
      now[a][b].second = p.first;
      q.emplace(a, b);
    }
  }
  if (now[0][s].first == -1)
    puts("-1");
  else {
    vector<long long> ans;
    long long a = 0;
    long long b = s;
    while (!(a == 0 && b == 0)) {
      ans.push_back(now[a][b].first);
      long long tmp = b - now[a][b].first;
      a = now[a][b].second;
      b = tmp;
    }
    reverse((ans).begin(), (ans).end());
    for (auto i : ans) cout << i;
    cout << endl;
  }
}