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;
namespace FI {
const int SIZE = 1 << 18 | 1;
char buf[SIZE], *front, *back;
void NextChar(char &c) {
  if (front == back) back = (front = buf) + fread(buf, 1, SIZE, stdin);
  c = (front == back) ? (char)EOF : *front++;
}
template <typename T>
void NextNum(T &x) {
  char c;
  int f = 1;
  for (NextChar(c); c > '9' || c < '0'; NextChar(c))
    if (c == '-') f = -1;
  for (x = 0; c >= '0' && c <= '9'; NextChar(c))
    x = (x << 3) + (x << 1) + c - '0';
  x *= f;
}
}  // namespace FI
const int maxd = 500 + 47;
const int maxs = 5000 + 47;
int d, s;
bool f[maxs][maxd];
pair<int, int> pre[maxs][maxd];
int a[maxs][maxd], ans[maxd * maxs];
queue<pair<int, int> > q;
int main() {
  scanf("%d%d", &d, &s);
  f[0][0] = true;
  q.push(make_pair(0, 0));
  while (!q.empty()) {
    pair<int, int> now = q.front();
    q.pop();
    for (int k = (0); k <= (9); k++) {
      if (now.first + k <= s && !f[now.first + k][(now.second * 10 + k) % d]) {
        f[now.first + k][(now.second * 10 + k) % d] = true;
        pre[now.first + k][(now.second * 10 + k) % d] = now;
        a[now.first + k][(now.second * 10 + k) % d] = k;
        q.push(make_pair(now.first + k, (now.second * 10 + k) % d));
      }
    }
  }
  if (!f[s][0])
    puts("-1");
  else {
    pair<int, int> now = make_pair(s, 0);
    pair<int, int> s = make_pair(0, 0);
    while (now != s) {
      ans[++ans[0]] = a[now.first][now.second];
      now = pre[now.first][now.second];
    }
    for (int i = (ans[0]); i >= (1); i--) printf("%d", ans[i]);
    puts("");
  }
}