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 vis[501][5001];
int d, s;
string helper(int d, int s) {
  queue<pair<string, pair<int, int>>> q;
  q.push({"", {0, 0}});
  int dd, ss, d1, s1;
  string t;
  vis[0][0] = 1;
  while (!q.empty()) {
    t = q.front().first;
    dd = q.front().second.first;
    ss = q.front().second.second;
    q.pop();
    if (dd == 0 && ss == s) return t;
    for (int i = 0; i <= 9; i++) {
      d1 = (dd * 10 + i) % d;
      s1 = ss + i;
      if (vis[d1][s1] == 0 && s1 <= s) {
        vis[d1][s1] = 1;
        q.push({t + char('0' + i), {d1, s1}});
      }
    }
  }
  return "-1";
}
int main() {
  cin >> d >> s;
  string ans = helper(d, s);
  cout << ans;
  return 0;
}