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;
long long a, b, oj[501][5001], od[501][5001], licz[501][5001], modo, pozx, poz,
    suma;
queue<pair<pair<long long, long long>, pair<long long, long long> > > q;
string w;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> a >> b;
  if (b == 0) {
    cout << 0;
    return 0;
  }
  oj[0][b] = -10;
  for (int i = 1; i <= min(b, 9LL); i++) {
    q.push(make_pair(make_pair(i, i % a), make_pair(i, -1)));
    od[i % a][i] = 1;
  }
  while (q.size() > 0) {
    licz[q.front().first.second][q.front().second.first] =
        q.front().first.first;
    od[q.front().first.second][q.front().second.first] = 1;
    modo = q.front().first.second;
    pozx = q.front().second.first;
    oj[q.front().first.second][q.front().second.first] =
        q.front().second.second;
    q.pop();
    for (long long i = 0; i <= min(9LL, b); i++) {
      if (od[(modo * 10 + i) % a][pozx + i] == 0 && pozx + i <= b) {
        q.push(make_pair(make_pair(i, (modo * 10 + i) % a),
                         make_pair(pozx + i, modo * 50000 + pozx)));
        od[(modo * 10 + i) % a][pozx + i] = 1;
      }
    }
  }
  if (oj[0][b] == -10) {
    cout << -1 << endl;
    return 0;
  }
  poz = b;
  while (poz != -1) {
    modo = poz / 50000;
    suma = poz % 50000;
    w += (licz[modo][suma] + '0');
    poz = oj[modo][suma];
  }
  for (long long i = w.size() - 1; i >= 0; i--) {
    cout << w[i];
  }
  return 0;
}