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;
int main() {
  int D, S;
  cin >> D >> S;
  vector<vector<bool>> visited(D, vector<bool>(S + 1));
  vector<vector<pair<int, int>>> pnt(D, vector<pair<int, int>>(S + 1));
  queue<pair<int, int>> Q;
  Q.push(make_pair(0, 0));
  visited[0][0] = true;
  while (!Q.empty()) {
    auto front = Q.front();
    Q.pop();
    for (int i = 0; i < 10 && front.second + i <= S; i++) {
      int mod = (front.first * 10 + i) % D;
      int sum = front.second + i;
      if (!visited[mod][sum]) {
        visited[mod][sum] = true;
        pnt[mod][sum] = front;
        Q.push(make_pair(mod, sum));
      }
    }
  }
  if (!visited[0][S]) {
    cout << -1 << endl;
  } else {
    string s;
    auto p = make_pair(0, S);
    while (p.first || p.second) {
      auto p1 = pnt[p.first][p.second];
      s.push_back('0' + p.second - p1.second);
      p = p1;
    }
    reverse(begin(s), end(s));
    cout << s << endl;
  }
  return 0;
}