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;
class node {
 public:
  char ans[700];
  long long int rem, sum, at;
};
long long int d, s;
bool vis[5005][500];
int main() {
  int begtime = clock();
  ;
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  cin >> d >> s;
  queue<node> q;
  node n;
  n.rem = 0;
  n.sum = 0;
  n.at = 0;
  q.push(n);
  while (q.size()) {
    node tmp = q.front();
    q.pop();
    for (long long int i = 0; i < 10; i++) {
      node n = tmp;
      n.ans[n.at] = '0' + i;
      n.at++;
      n.rem = (10 * tmp.rem + i) % d;
      n.sum += i;
      if (n.sum > s || vis[n.sum][n.rem]) continue;
      if (n.rem == 0 && n.sum == s) {
        for (long long int i = 0; i < n.at; i++) cout << n.ans[i];
        int endtime = clock();
        cerr << "\n\n"
             << "Time elapsed: " << (endtime - begtime) * 1000 / CLOCKS_PER_SEC
             << " ms\n\n";
        return 0;
      }
      vis[n.sum][n.rem] = 1;
      q.push(n);
    }
  }
  cout << -1;
  int endtime = clock();
  cerr << "\n\n"
       << "Time elapsed: " << (endtime - begtime) * 1000 / CLOCKS_PER_SEC
       << " ms\n\n";
  return 0;
}