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;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
const int dax = 500;
const int sax = 5001;
const int K = 10;
const int M = 1010000;
int dp[dax][sax];
vector<int> pr[dax][sax];
int main() {
  ios_base::sync_with_stdio(false);
  int d, s;
  vector<int> potega(M);
  cin >> d >> s;
  potega[0] = 1;
  for (int i = (1); i <= (M - 1); ++i) potega[i] = (potega[i - 1] * 10) % d;
  for (int j = 0; j < (dax); ++j)
    for (int k = 0; k < (sax); ++k) dp[j][k] = -1;
  queue<pair<int, int> > Q;
  dp[0][0] = 0;
  Q.push({0, 0});
  while (!Q.empty()) {
    auto curr = Q.front();
    Q.pop();
    int remainder = curr.first;
    int sum_of_digits = curr.second;
    int pozycja = dp[remainder][sum_of_digits];
    for (int new_cyf = 0; new_cyf < (K); ++new_cyf) {
      int new_remainder = (remainder * 10 + new_cyf) % d;
      int new_sum_of_digits = sum_of_digits + new_cyf;
      if (new_sum_of_digits <= s &&
          (dp[new_remainder][new_sum_of_digits] == -1)) {
        dp[new_remainder][new_sum_of_digits] = pozycja + 1;
        pr[new_remainder][new_sum_of_digits] = {new_cyf, remainder,
                                                sum_of_digits};
        Q.push({new_remainder, new_sum_of_digits});
      }
    }
  }
  if (dp[0][s] == -1) {
    printf("-1\n");
    return 0;
  }
  int modulo = 0;
  int suma = s;
  vector<int> rr;
  for (int i = 0; i < (dp[0][s]); ++i) {
    auto pop = pr[modulo][suma];
    rr.push_back(pop[0]);
    modulo = pop[1];
    suma = pop[2];
  }
  for (int i = ((int)(((int)((rr).size())))) - 1; i >= (0); --i)
    printf("%d", rr[i]);
  printf("\n");
}