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 long long inf = (long long)2e9;
const long long md = 1000000007;
long long dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
long long power(long long a, long long p, long long md) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans *= a;
    p /= 2;
    a *= a;
    ans %= md;
    a %= md;
  }
  return ans;
}
long long mdinv(long long a) { return power(a, md - 2, md); }
const long long mxd = 520, mxs = 5200;
long long dis[mxd][mxs];
long long d, s;
void bfs() {
  for (long long i = 0; i < (long long)mxd; i++)
    for (long long j = 0; j < (long long)mxs; j++) dis[i][j] = inf;
  queue<pair<long long, long long> > q;
  q.push({0, 0});
  dis[0][0] = 0;
  while (!q.empty()) {
    auto p = q.front();
    q.pop();
    long long cmod = p.first, csum = p.second;
    if (csum > s) continue;
    for (long long i = 0; i < (long long)10; i++) {
      long long nmod = (cmod * 10 + i) % d;
      long long nsum = csum + i;
      if (dis[nmod][nsum] > dis[cmod][csum] + 1) {
        dis[nmod][nsum] = dis[cmod][csum] + 1;
        q.push({nmod, nsum});
      }
    }
  }
  long long dig = dis[0][s];
  if (dig == inf) {
    cout << -1;
    return;
  }
  vector<long long> ans;
  pair<long long, long long> curState = {0, s};
  for (long long fit = 0; fit < (long long)dig; fit++) {
    for (long long i = 0; i < (long long)10; i++) {
      long long nmod =
          ((curState.first - i * power(10, (dig - 1 - fit), d)) % d + d) % d;
      long long nsum = curState.second - i;
      if (nsum < 0) continue;
      if (dis[nmod][nsum] + 1 <= dis[curState.first][curState.second]) {
        ans.push_back(i);
        for (long long addt = 0;
             addt < (long long)-dis[nmod][nsum] - 1 +
                        dis[curState.first][curState.second];
             addt++) {
          ans.push_back(0);
          fit++;
        }
        curState = {nmod, nsum};
        break;
      }
    }
  }
  for (long long i : ans) cout << i;
}
signed main() {
  cin >> d >> s;
  bfs();
}