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 N = 504;
inline long long read() {
  long long s = 0, w = 1;
  register char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
  return s * w;
}
long long D, S;
long long book[N][N * 10];
pair<long long, long long> pre[N][N * 10];
queue<pair<long long, long long> > Q;
signed main() {
  D = read(), S = read();
  for (register long long i = 1; i < 10; i++) {
    long long p = i % D;
    if (!book[p][i]) {
      book[p][i] = 1;
      Q.push(make_pair(p, i));
      pre[p][i] = make_pair(0, i);
    }
  }
  while (!Q.empty()) {
    pair<long long, long long> x = Q.front();
    Q.pop();
    if (x.second > S) continue;
    if (x == make_pair(0ll, S)) {
      vector<long long> F;
      while (x.second) {
        pair<long long, long long> y = pre[x.first][x.second];
        F.emplace_back(y.second);
        x.first = y.first, x.second -= y.second;
      }
      reverse(F.begin(), F.end());
      for (register long long i = 0; i < (long long)F.size(); i++)
        printf("%lld", F[i]);
      puts("");
      return 0;
    }
    for (register long long i = 0; i < 10; i++) {
      long long u = (x.first * 10 + i) % D;
      long long v = x.second + i;
      if (book[u][v]) continue;
      book[u][v] = 1;
      pre[u][v] = make_pair(x.first, i);
      Q.push(make_pair(u, v));
    }
  }
  puts("-1");
  return 0;
}