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;
vector<vector<pair<int, int> > > dist;
void write(int a, int b) {
  if (a == 0 && b == 0) return;
  pair<int, int> p = dist[a][b];
  write(p.first, p.second);
  cout << b - p.second;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int d, s;
  cin >> d >> s;
  dist = vector<vector<pair<int, int> > >(
      d, vector<pair<int, int> >(s + 1, {-1, -1}));
  dist[0][0] = {0, 0};
  queue<pair<int, int> > q;
  q.push({0, 0});
  while (!q.empty()) {
    pair<int, int> p = q.front();
    q.pop();
    for (int i = 0; i <= 9; ++i) {
      if (p.second + i <= s &&
          dist[(10 * p.first + i) % d][p.second + i].first == -1) {
        dist[(10 * p.first + i) % d][p.second + i] = p;
        q.push({(10 * p.first + i) % d, p.second + i});
      }
    }
  }
  if (dist[0][s].first == -1)
    cout << -1 << endl;
  else {
    write(0, s);
    cout << endl;
  }
}