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 MAXD = 5e2 + 6.9;
const long long MAXS = 5e3 + 69;
struct vl {
  long long mod, sum;
};
long long d, s;
long long lastdigit[MAXD][MAXS];
vl last[MAXD][MAXS];
void bfs() {
  for (long long mod = 0; mod < d; mod++)
    for (long long sum = 0; sum <= s; sum++) lastdigit[mod][sum] = -1;
  queue<vl> q;
  for (long long i = 1; i <= 9; i++)
    lastdigit[i % d][i] = i, q.push({i % d, i});
  while (!q.empty()) {
    long long mod = q.front().mod;
    long long sum = q.front().sum;
    q.pop();
    for (long long nex = 0; nex <= 9; nex++) {
      long long nmod = (mod * 10 + nex) % d;
      long long nsum = sum + nex;
      if (nsum > s || lastdigit[nmod][nsum] != -1) continue;
      lastdigit[nmod][nsum] = nex;
      last[nmod][nsum] = {mod, sum};
      q.push({nmod, nsum});
    }
  }
}
void tray(vl u) {
  if (lastdigit[u.mod][u.sum] != -1) {
    tray(last[u.mod][u.sum]);
    cout << lastdigit[u.mod][u.sum];
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> d >> s;
  bfs();
  if (lastdigit[0][s] == -1)
    cout << -1;
  else
    tray({0, s});
}