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 int N = 2e3 + 7, maxn = 1e5 + 7;
bool in[507][5007];
int dp[507][5007], pre[507][5007];
vector<int> ans;
struct qwe {
  int x, y, px, py, z;
};
queue<qwe> q;
int main() {
  int n, m;
  cin >> n >> m;
  memset(dp, -1, sizeof(dp));
  for (int i = (1); i < (10); ++i) {
    qwe tmp;
    tmp.x = i % n;
    tmp.y = i;
    tmp.z = i;
    tmp.px = -1;
    tmp.py = -1;
    q.push(tmp);
  }
  qwe u;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    if (u.y > m || in[u.x][u.y]) continue;
    in[u.x][u.y] = 1;
    pre[u.x][u.y] = u.px * 1e4 + u.py;
    dp[u.x][u.y] = u.z;
    if (u.x == 0 && u.y == m) break;
    qwe v;
    for (int i = (0); i < (10); ++i) {
      v.x = (u.x * 10 + i) % n;
      v.y = u.y + i;
      v.z = i;
      v.px = u.x;
      v.py = u.y;
      q.push(v);
    }
  }
  if (in[0][m] == 0)
    printf("-1");
  else {
    int x = 0, y = m, t1, t2;
    while (1) {
      ans.push_back(dp[x][y]);
      t1 = pre[x][y] / (int)(1e4);
      t2 = pre[x][y] % (int)(1e4);
      if (t1 < 0 && t2 < 0) break;
      x = t1, y = t2;
    }
    for (int i = (ans.size()) - 1; i >= (0); --i) {
      printf("%d", ans[i]);
    }
  }
}