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 <typename T>
void write(ostream& out, T t) {
  out << t << "\n";
}
template <typename T, typename... Args>
void write(ostream& out, T t, Args... args) {
  out << t << ' ';
  write(out, args...);
}
template <typename... Args>
void debug(Args... args) {}
template <typename T>
inline T abs(T t) {
  return t < 0 ? -t : t;
}
const long long modn = 1000000007;
inline long long mod(long long x) { return x % modn; }
const int INF = 0x3f3f3f3f;
int n, m, k;
int prof;
int dp[5123][512];
pair<int, int> lst[5123][512];
int lstd[5123][512];
queue<pair<int, int> > qu;
int main() {
  int som;
  scanf("%d%d", &k, &som);
  int mn = INT_MAX;
  memset(dp, -1, sizeof(dp));
  for (int d = 1; d <= min(som, 9); d++) {
    fflush(stdout);
    lst[som - d][(d % k)] = {som, 0};
    lstd[som - d][(d % k)] = d;
    dp[som - d][(d % k)] = 1;
    qu.push({som - d, d % k});
  }
  while (!qu.empty()) {
    pair<int, int> to = qu.front();
    qu.pop();
    int s = to.first;
    int r = to.second;
    for (int d = 0; d <= 9; d++) {
      int ns = s - d, nr = (10 * r + d) % k;
      if (ns >= 0 && dp[ns][nr] == -1) {
        if (dp[ns][nr] == -1) qu.push({ns, nr});
        dp[ns][nr] = dp[s][r] + 1;
        lst[ns][nr] = {s, r};
        lstd[ns][nr] = d;
      }
    }
  }
  if (dp[0][0] == -1) {
    puts("-1");
    return 0;
  }
  int s = 0, r = 0;
  stack<int> ans;
  while (s != som || r != 0) {
    pair<int, int> bef = lst[s][r];
    ans.push(lstd[s][r]);
    s = bef.first;
    r = bef.second;
  }
  while (!ans.empty()) {
    printf("%d", ans.top());
    ans.pop();
  }
  puts("");
}