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;
void smain();
int main() {
  ios_base::sync_with_stdio(0);
  smain();
  return 0;
}
void solve(long long d, long long s);
void smain() {
  for (long long d, s; cin >> d >> s;) {
    solve(d, s);
    cerr << endl;
  }
}
constexpr long long D = 500;
constexpr long long S = 5000;
bool used[D + 1][S + 1];
pair<long long, long long> parent[D + 1][S + 1];
long long digit[D + 1][S + 1];
void solve(long long d, long long s) {
  for (long long i = 0; i <= D; ++i)
    for (long long j = 0; j <= S; ++j) used[i][j] = false;
  queue<pair<long long, long long>> q;
  q.push({0, s});
  used[0][s] = true;
  while (!q.empty()) {
    auto p = q.front();
    q.pop();
    for (long long i = 0; i <= 9; ++i) {
      long long nr = (p.first * 10 + i) % d;
      long long ns = p.second - i;
      if (ns < 0) continue;
      if (used[nr][ns]) continue;
      used[nr][ns] = true;
      parent[nr][ns] = p;
      digit[nr][ns] = i;
      q.push({nr, ns});
    }
  }
  if (!used[0][0])
    cout << -1 << endl;
  else {
    string number;
    pair<long long, long long> p(0, 0);
    while (p.first != 0 || p.second != s) {
      number.push_back(digit[p.first][p.second] + '0');
      p = parent[p.first][p.second];
    }
    reverse(number.begin(), number.end());
    cout << number << endl;
  }
}