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 = 505, S = 5015;
int d, s, num, sum, vis[D][S];
pair<int, int> pre[D][S];
void ans(int num, int sum) {
  if (sum == 0) {
    return;
  }
  int pnum = pre[num][sum].first, psum = pre[num][sum].second;
  ans(pnum, psum);
  cout << sum - psum;
}
int main() {
  cin >> d >> s;
  queue<pair<int, int>> q;
  q.push({0, 0});
  vis[0][0] = 1;
  while (not(num == 0 and sum == s) and not q.empty()) {
    tie(num, sum) = q.front();
    q.pop();
    for (int i = 0; i < 10; i++) {
      int nnum = (num * 10 + i) % d, nsum = sum + i;
      if (vis[nnum][nsum] or nsum > s) continue;
      q.push({nnum, nsum});
      vis[nnum][nsum] = 1;
      pre[nnum][nsum] = {num, sum};
    }
  }
  if (not vis[0][s]) {
    return cout << -1, 0;
  }
  ans(num, sum);
}