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;
struct num {
  int mod, sum, val;
} f[510][5010];
queue<num> q;
int d, s, ans1, ans[10000000];
void print() {
  ans1 = 0;
  num x;
  x.mod = x.val = 0;
  x.sum = s;
  while (f[x.mod][x.sum].val != -1) {
    ans[++ans1] = f[x.mod][x.sum].val;
    x = f[x.mod][x.sum];
  }
  for (int i = ans1 - 1; i >= 1; i--) printf("%d", ans[i]);
}
int main() {
  memset(f, -1, sizeof f);
  cin >> d >> s;
  num st;
  f[0][0].val = 0;
  f[0][0].mod = d + 1, f[0][0].sum = s + 1;
  f[d + 1][s + 1].val = -1;
  st.mod = 0, st.sum = 0;
  q.push((num)st);
  while (!q.empty()) {
    num tmp = q.front();
    q.pop();
    for (int i = 0; i <= 9; i++) {
      if (tmp.sum + i <= s) {
        num nxt;
        nxt.mod = (tmp.mod * 10 + i) % d;
        nxt.sum = tmp.sum + i;
        if (f[nxt.mod][nxt.sum].val != -1) continue;
        f[nxt.mod][nxt.sum] = tmp;
        f[nxt.mod][nxt.sum].val = i;
        q.push((num)nxt);
        if (!nxt.mod && nxt.sum == s) {
          print();
          return 0;
        }
      }
    }
  }
  cout << -1;
}