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>
T input() {
  T res;
  cin >> res;
  {};
  return res;
}
template <typename IT>
void input_seq(IT b, IT e) {
  std::generate(b, e,
                input<typename std::remove_reference<decltype(*b)>::type>);
}
int main() {
  iostream::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int d = input<int>();
  int s = input<int>();
  vector<vector<pair<int, int>>> rgraph(d);
  for (int rem = 0; rem < d; ++rem)
    for (int dig = 0; dig < 10; ++dig)
      rgraph[(rem * 10 + dig) % d].emplace_back(dig, rem);
  queue<pair<int, int>> q;
  vector<vector<int>> dist(s + 1,
                           vector<int>(d, std::numeric_limits<int>::max()));
  dist[s][0] = 0;
  q.emplace(s, 0);
  while (not q.empty()) {
    int sm = q.front().first;
    int rm = q.front().second;
    q.pop();
    for (auto go : rgraph[rm])
      if (sm >= go.first and
          dist[sm - go.first][go.second] > dist[sm][rm] + 1) {
        dist[sm - go.first][go.second] = dist[sm][rm] + 1;
        q.emplace(sm - go.first, go.second);
      }
  }
  if (dist[0][0] == std::numeric_limits<int>::max()) {
    cout << "-1\n";
    return 0;
  }
  string ans = "";
  int sm = 0;
  int rm = 0;
  while (make_pair(sm, rm) != make_pair(s, 0)) {
    bool ok = false;
    for (int dig = 0; dig < 10 and sm + dig <= s; ++dig) {
      int nsum = sm + dig;
      int nrm = (rm * 10 + dig) % d;
      if (dist[sm][rm] == dist[nsum][nrm] + 1) {
        sm = nsum;
        rm = nrm;
        ans += char('0' + dig);
        ok = true;
        break;
      }
    }
    assert(ok);
  }
  cout << ans << "\n";
  return 0;
}