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 = (int)1e7 + 15;
const long long inf = 0x3f3f3f3f3f3f3f3f;
struct Data {
  bool used;
  int val;
  pair<int, int> pre;
  Data() : used(false), val(0), pre(-1, -1) {}
};
Data dat[505][5005];
int main() {
  int d, s;
  while (~scanf("%d%d", &d, &s)) {
    queue<pair<int, int> > que;
    que.push(make_pair(0, 0));
    dat[0][0].used = true;
    while (!que.empty()) {
      pair<int, int> ele = que.front();
      que.pop();
      for (int k = 0; k <= 9; k++) {
        if (ele.second + k > s) {
          continue;
        }
        int nx = (ele.first * 10 + k) % d;
        int ny = (ele.second + k);
        if (!dat[nx][ny].used) {
          dat[nx][ny].used = true;
          dat[nx][ny].val = k;
          dat[nx][ny].pre = ele;
          que.push(make_pair(nx, ny));
        }
      }
    }
    if (!dat[0][s].used) {
      puts("-1");
    } else {
      string str;
      pair<int, int> pr(0, s);
      while (pr.first != -1 && pr.second != -1) {
        str.push_back(dat[pr.first][pr.second].val + '0');
        pr = dat[pr.first][pr.second].pre;
      }
      reverse(str.begin(), str.end());
      puts(str.c_str() + 1);
    }
  }
  return 0;
}