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>
#pragma GCC optimize("O3")
using namespace std;
template <class T>
T Gcd(T x, T y) {
  return y ? Gcd(y, x % y) : x;
}
template <class T>
T Lcm(T x, T y) {
  return x / Gcd(x, y) * y;
}
const long long MOD = 1000000007LL;
const int M = 5005;
const int N = 505;
int f[M][N], to[M][N], n, m, tx, ty, op, ed, ans[N * M];
pair<int, int> d[N * M];
int main() {
  scanf("%d %d", &n, &m);
  memset((f), (-1), sizeof((f)));
  memset((to), (-1), sizeof((to)));
  f[0][0] = 0;
  d[1] = make_pair(0, 0);
  for (op = ed = 1; op <= ed; op++) {
    for (int i = 0; i < 10; i++) {
      ty = (d[op].second * 10 + i) % n;
      tx = d[op].first + i;
      if (f[tx][ty] < 0 && tx <= m) {
        d[++ed] = make_pair(tx, ty);
        f[tx][ty] = i;
        to[tx][ty] = d[op].second;
      }
    }
  }
  ed = 0;
  if (f[m][0] < 0)
    puts("-1");
  else {
    tx = m;
    ty = 0;
    while (to[tx][ty] >= 0) {
      ans[++ed] = f[tx][ty];
      ty = to[tx][ty];
      tx -= ans[ed];
    }
    for (int i = ed; i >= 1; i--) printf("%d", ans[i]);
  }
  return 0;
}