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;
int R[5 << 10][512];
pair<int, int> D[5 << 10][512];
int main() {
  int d, s;
  scanf("%d%d", &d, &s);
  memset(R, -1, sizeof(R));
  int i, j, k;
  queue<pair<int, int> > q;
  memset(R, -1, sizeof(R));
  for (i = (1); i < (10); ++i) {
    j = i % d;
    R[i][j] = 1;
    D[i][j] = pair<int, int>(i, 0);
    q.push(pair<int, int>(i, j));
  }
  while (!q.empty()) {
    i = q.front().first;
    j = q.front().second;
    q.pop();
    for (k = (0); k < (10); ++k) {
      int ii = i + k;
      int jj = (j * 10 + k) % d;
      if (ii <= s && R[ii][jj] == -1) {
        R[ii][jj] = R[i][j] + 1;
        D[ii][jj] = pair<int, int>(k, j);
        q.push(pair<int, int>(ii, jj));
      }
    }
  }
  if (R[s][0] == -1)
    printf("-1\n");
  else {
    i = s;
    j = 0;
    string res = "";
    while (i != 0) {
      pair<int, int> t = D[i][j];
      i -= t.first;
      j = t.second;
      res.push_back('0' + t.first);
    }
    reverse((res).begin(), (res).end());
    printf("%s\n", res.c_str());
  }
  return 0;
};