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;
bool vis[500][5001];
int D[500][5001];
int R[500][5001];
queue<pair<int, int> > q;
void solve(int d, int s) {
  q.push(make_pair(0, 0));
  while (q.size() && !vis[0][s]) {
    pair<int, int> p = q.front();
    q.pop();
    vis[0][0] = true;
    for (int i = 0; i < 10; i++) {
      if (!i && !p.second) continue;
      int sm = p.second + i;
      int r = (p.first * 10 + i) % d;
      if (vis[r][sm] || sm > s) continue;
      vis[r][sm] = true;
      D[r][sm] = i;
      R[r][sm] = p.first;
      if (r == 0 && sm == s) break;
      ;
      q.push(make_pair(r, sm));
    }
  }
  if (vis[0][s]) {
    int r = 0, sm = s;
    string ans;
    while (1) {
      if (r == 0 && sm == 0) break;
      ans += D[r][sm] + '0';
      int tmp = sm;
      sm -= D[r][sm];
      r = R[r][tmp];
    }
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
  } else {
    printf("%d\n", -1);
  }
}
int main() {
  int d, s;
  scanf("%d%d", &d, &s);
  solve(d, s);
  return 0;
}