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;
template <class T>
void cmax(T& x, T y) {
  if (x < y) x = y;
}
template <class T>
void cmin(T& x, T y) {
  if (x > y) x = y;
}
struct frstream {
  int c, f;
  operator void*() { return ~c ? this : nullptr; }
  frstream& operator>>(char* str) {
    c = scanf("%s", str);
    return *this;
  }
  frstream& operator>>(double& x) {
    c = scanf("%lf", &x);
    return *this;
  }
  template <class T>
  frstream& operator>>(T& x) {
    for (f = 0; ~c && (c < 48 || c > 57); c = getchar()) {
      if (c == '-') f = 1;
    }
    for (x = 0; c > 47 && c < 58; c = getchar()) x = x * 10 + (c ^ 48);
    if (f) {
      x = -x;
    }
    return *this;
  }
} read;
const int maxn = 5e3 + 10, INF = 0x3f3f3f3f;
const long long LINF = (long long)INF << 32 | INF, mod = 1e9 + 7;
struct Node {
  int res, sum;
  Node(int a, int b) : res(a), sum(b) {}
};
const int N = 510;
int last[maxn][N], pre[maxn][N][2];
bool vis[maxn][N];
void print(int s, int r) {
  if (!s && !r) return;
  print(pre[s][r][0], pre[s][r][1]);
  putchar('0' + last[s][r]);
}
int main() {
  queue<Node> q;
  int p, x;
  read >> p >> x;
  vis[0][0] = true;
  q.push(Node(0, 0));
  while (!q.empty()) {
    int r = q.front().res, s = q.front().sum;
    q.pop();
    for (int i = 0; i < (10); ++i) {
      int nxtr = (10 * r + i) % p;
      int nxts = s + i;
      if (nxts > x || vis[nxts][nxtr]) continue;
      vis[nxts][nxtr] = true;
      pre[nxts][nxtr][0] = s;
      pre[nxts][nxtr][1] = r;
      last[nxts][nxtr] = i;
      q.push(Node(nxtr, nxts));
    }
  }
  if (vis[x][0])
    print(x, 0);
  else
    puts("-1");
  return 0;
}