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;
string BFS(const int &n, const int &sum);
int main() {
  int n, digit_sum;
  cin >> n >> digit_sum;
  cout << BFS(n, digit_sum);
  return 0;
}
string BFS(const int &n, const int &sum) {
  bool IsVisisted[5005][505] = {false};
  queue<tuple<int, int, string> > q;
  q.push(tuple<int, int, string>(0, 0, ""));
  while (!q.empty()) {
    auto tmp = q.front();
    q.pop();
    if (get<0>(tmp) == sum and get<1>(tmp) == 0) return get<2>(tmp);
    for (int i = (get<2>(tmp) == "" ? 1 : 0); i < 10; i++) {
      auto SUM = get<0>(tmp) + i;
      auto MOD = (10 * get<1>(tmp) + i % n) % n;
      if (SUM <= sum and !IsVisisted[SUM][MOD]) {
        IsVisisted[SUM][MOD] = true;
        q.push(tuple<int, int, string>(SUM, MOD, get<2>(tmp) + char(i + 48)));
      }
    }
  }
  return "-1";
}