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;
using ll = long long;
void solve(istream &cin = std::cin, ostream &cout = std::cout) {
  int d, s;
  cin >> d >> s;
  vector<int> dist(d * (s + 1), -1);
  auto par = dist, dig = dist;
  auto state = [&](int x, int y) { return x * d + y; };
  auto decode = [&](int x) { return pair<int, int>{x / d, x % d}; };
  queue<int> q;
  dist[state(0, 0)] = 0;
  q.push(state(0, 0));
  while (!q.empty()) {
    int cur = q.front();
    int sum, rem;
    tie(sum, rem) = decode(cur);
    q.pop();
    for (int i = 0; i < 10; i++) {
      int sum_to = sum + i;
      int rem_to = (rem * 10 + i) % d;
      if (sum_to > s) continue;
      int to = state(sum_to, rem_to);
      if (dist[to] == -1) {
        dist[to] = dist[cur] + 1;
        par[to] = cur;
        dig[to] = i;
        q.push(to);
      }
    }
  }
  if (dist[state(s, 0)] == -1)
    cout << -1 << endl;
  else {
    string ans;
    int cur = state(s, 0);
    while (par[cur] != -1) {
      ans += dig[cur] + '0';
      cur = par[cur];
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed;
  cout << setprecision(20);
  solve();
  return 0;
}