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;
class Timer {
  clock_t start;
  string name;

 public:
  Timer() {
    name = "";
    start = clock();
  }
  Timer(string s) {
    name = s;
    start = clock();
  }
  ~Timer() {
    fprintf(stderr, "%s: %.3gs\n", name.c_str(),
            1.0 * (clock() - start) / CLOCKS_PER_SEC);
  }
};
const double EPS = 1e-9;
const long double PI = acos(-1.0L);
template <typename dtype>
inline dtype sq(dtype a) {
  return a * a;
}
template <typename dtype1, typename dtype2>
inline pair<dtype1, dtype2> mp(dtype1 a, dtype2 b) {
  return make_pair(a, b);
}
template <typename dtype1, typename dtype2>
inline dtype1 safeMod(dtype1 a, dtype2 m) {
  return (a % m + m) % m;
}
template <typename dtype1, typename dtype2>
inline bool isEq(dtype1 a, dtype2 b) {
  return abs(a - b) < EPS;
}
template <typename dtype1, typename dtype2, typename dtype3>
inline bool isEq(dtype1 a, dtype2 b, dtype3 eps) {
  return abs(a - b) < eps;
}
template <typename dtype>
inline dtype toRad(dtype deg) {
  return deg * PI / 180.0;
}
template <typename dtype>
inline dtype toDeg(dtype rad) {
  return rad * 180.0 / PI;
}
template <typename dtype>
inline bool isKthBitOn(dtype n, int k) {
  assert(n <= numeric_limits<dtype>::max());
  assert(k <= numeric_limits<dtype>::digits);
  dtype ONE = 1;
  return bool((n & (ONE << k)));
}
template <typename dtype>
inline void setKthBit(dtype& n, int k) {
  assert(n <= numeric_limits<dtype>::max());
  assert(k <= numeric_limits<dtype>::digits);
  dtype ONE = 1;
  n = (n | (ONE << k));
}
const int oo = 0x3f3f3f3f;
const int MAX = 200010;
const int MOD = 1000000007;
const int precision = 10;
int d, s;
bool vis[50000000];
int parent[50000000];
int wrap(int rem, int ds, int p) { return (rem * 10000 + ds) * 10 + p; }
tuple<int, int, int> unwrap(int n) {
  int p = n % 10;
  n /= 10;
  int ds = n % 10000;
  n /= 10000;
  return make_tuple(n, ds, p);
}
void printAns(int v) {
  if (parent[v] == -1) return;
  printAns(parent[v]);
  printf("%d", get<2>(unwrap(v)));
}
bool bfs() {
  queue<int> q;
  int st = wrap(0, 0, 0);
  q.push(st);
  vis[st] = true;
  parent[st] = -1;
  int r, ds, p, v, u;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    tie(r, ds, p) = unwrap(u);
    for (int i = 0; i < 10; i++) {
      v = wrap((r * 10 + i) % d, i + ds, i);
      if (i + ds <= s && !vis[v]) {
        vis[v] = true;
        parent[v] = u;
        q.push(v);
        if ((r * 10 + i) % d == 0 && i + ds == s) {
          printAns(v);
          return true;
        }
      }
    }
  }
  return false;
}
int main(int argc, char* argv[]) {
  scanf("%d %d", &d, &s);
  if (!bfs()) printf("-1");
  return 0;
}