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 N = 1e5 + 2, inf = 1e18;
struct data {
  string number;
  int modulo = 0;
  int sum_of_digits = 0;
};
bool visited[505][5005];
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int d, s;
  cin >> d >> s;
  queue<data> Q;
  for (int dig = 1; dig <= 9; dig++) {
    if (dig <= s) {
      data add;
      add.number = to_string(dig);
      add.modulo = dig % d;
      add.sum_of_digits = dig;
      if (visited[add.modulo][add.sum_of_digits] == false) {
        Q.push(add);
        visited[add.modulo][add.sum_of_digits] = true;
      }
    }
  }
  while (!Q.empty()) {
    data curr = Q.front();
    Q.pop();
    if (curr.modulo == 0 && curr.sum_of_digits == s) {
      cout << curr.number << '\n';
      return 0;
    }
    for (int dig = 0; dig <= 9; dig++) {
      data next;
      next.modulo = (curr.modulo * 10 + dig) % d;
      next.sum_of_digits = curr.sum_of_digits + dig;
      if (next.sum_of_digits <= s and
          visited[next.modulo][next.sum_of_digits] == false) {
        next.number = curr.number;
        next.number.push_back((char)(dig + '0'));
        visited[next.modulo][next.sum_of_digits] = true;
        Q.push(next);
      }
    }
  }
  cout << -1 << '\n';
}