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;
const int D = 510, S = 5010, inf = 1e9;
int dist[D][S];
pair<int, int> back[D][S];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int d, sum;
  cin >> d >> sum;
  for (int m = 0; m < d; ++m) {
    for (int s = 0; s <= sum; ++s) {
      dist[m][s] = inf;
    }
  }
  dist[0][0] = 0;
  queue<pair<int, int> > q;
  q.push({0, 0});
  while (!q.empty()) {
    int m, s;
    tie(m, s) = q.front();
    q.pop();
    for (int digit = 0; digit < 10 and s + digit <= sum; ++digit) {
      int new_m = ((10 * m) + digit) % d;
      int new_s = s + digit;
      if (dist[m][s] + 1 < dist[new_m][new_s]) {
        dist[new_m][new_s] = dist[m][s] + 1;
        back[new_m][new_s] = {m, s};
        q.push({new_m, new_s});
      }
    }
  }
  int m = 0, s = sum;
  if (dist[m][s] == inf) {
    cout << -1;
  } else {
    string ans = "";
    while (m != 0 or s != 0) {
      ans += (s - back[m][s].second) + '0';
      tie(m, s) = back[m][s];
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
  }
}