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 uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &item) {
  out << '(' << item.first << ", " << item.second << ')';
  return out;
}
template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  for (const auto &item : v) out << item << ' ';
  return out;
}
const int D = 510;
const int S = 5010;
bool dp[S][D];
pair<pii, int> prv[S][D];
queue<pii> q;
string reconstruct(int s, int r) {
  if (prv[s][r].second == -1) return "";
  return reconstruct(prv[s][r].first.first, prv[s][r].first.second) +
         char(prv[s][r].second + '0');
}
int main() {
  ios_base::sync_with_stdio(false);
  int d, s;
  cin >> d >> s;
  memset(dp, 0, sizeof dp);
  memset(prv, -1, sizeof prv);
  q.push({0, 0});
  dp[0][0] = true;
  while (!q.empty()) {
    int sd = q.front().first;
    int r = q.front().second;
    q.pop();
    for (int dig = 0; dig < 10; ++dig) {
      int newr = (r * 10 + dig) % d;
      if (sd + dig > s) continue;
      if (!dp[sd + dig][newr]) {
        dp[sd + dig][newr] = true;
        prv[sd + dig][newr] = {{sd, r}, dig};
        q.push({sd + dig, newr});
      }
    }
  }
  if (!dp[s][0])
    cout << -1 << '\n';
  else
    cout << reconstruct(s, 0) << '\n';
  return 0;
}