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>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
mt19937_64 mt_rand(chrono::system_clock::now().time_since_epoch().count());
template <typename T1, typename T2>
inline bool upmax(T1& a, T2 b) {
  return (a < b ? (a = b, true) : false);
}
template <typename T1, typename T2>
inline bool upmin(T1& a, T2 b) {
  return (b < a ? (a = b, true) : false);
}
const int maxn = (int)2e5 + 20;
const int maxlog = 21;
const int base = (int)1e9 + 7;
const long double eps = (long double)1e-7;
const long double PI = acos(-1.);
int d, s;
bool used[5001][501];
int f[5001][501];
int pp[maxn];
pair<int, int> to[5001][501][10];
int main() {
  cin >> d >> s;
  queue<pair<int, int> > q;
  pp[0] = 1 % d;
  for (int i = 1; i < maxn; i++) {
    pp[i] = (pp[i - 1] * 10) % d;
  }
  for (int i = 0; i <= s; i++)
    for (int j = 0; j < d; j++)
      for (int k = 0; k < 10; k++) to[i][j][k] = make_pair(base, base);
  for (int i = 0; i <= s; i++)
    for (int j = 0; j < d; j++) {
      f[i][j] = base;
      for (int k = 0; k < 10; k++) {
        if (i + k <= s) {
          to[i + k][(j * 10 + k) % d][k] = make_pair(i, j);
        }
      }
    }
  f[s][0] = 0;
  q.push(make_pair(s, 0));
  while (!q.empty()) {
    int sum = q.front().first, rem = q.front().second;
    q.pop();
    if (used[sum][rem]) continue;
    used[sum][rem] = true;
    for (int i = 0; i < 10; i++) {
      int new_sum = sum - i;
      if (new_sum >= 0) {
        int new_rem = (rem * 10 + i) % d;
        upmin(f[new_sum][new_rem], f[sum][rem] + 1);
        q.push(make_pair(new_sum, new_rem));
      }
    }
  }
  if (f[0][0] == base) {
    cout << -1;
    return 0;
  }
  int ans = f[0][0];
  string res;
  int sum = 0, rem = 0;
  for (int l = 0; l < ans; l++) {
    for (int i = (l == 0 ? 1 : 0); i < 10; i++) {
      int new_rem = (rem + pp[ans - l - 1] * i) % d;
      if (sum + i <= s && f[sum + i][(d - new_rem) % d] <= ans - l - 1) {
        res += char(i + '0');
        sum += i;
        rem = new_rem;
        break;
      }
    }
  }
  cout << res << "\n";
}