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;
class Timer {
 private:
  string scope_name;
  chrono::high_resolution_clock::time_point start_time;

 public:
  Timer(string name) : scope_name(name) {
    start_time = chrono::high_resolution_clock::now();
  }
  ~Timer() {
    auto stop_time = chrono::high_resolution_clock::now();
    auto length =
        chrono::duration_cast<chrono::microseconds>(stop_time - start_time)
            .count();
    double mlength = double(length) * 0.001;
    ;
  }
};
const long long MOD = 1000000007;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int iNF = 0x3f3f3f3f;
const long long MAXD = 502;
const long long MAXS = 5003;
int d, s, f, b;
bool vis[MAXD][MAXS];
char ans[MAXD][MAXS];
pair<int, int> from[MAXD][MAXS];
pair<int, int> state[MAXD * MAXS];
int main() {
  ;
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> d >> s;
  state[b++] = {0, 0};
  vis[0][0] = true;
  while (b > f) {
    pair<int, int> cur = state[f++];
    if (cur.first == 0 && cur.second == s) {
      break;
    }
    for (int i = 0; i < 10; i += 1) {
      int nd = (cur.first * 10 + i) % d;
      int ns = cur.second + i;
      if (ns <= s && !vis[nd][ns]) {
        vis[nd][ns] = true;
        ans[nd][ns] = char(i + '0');
        from[nd][ns] = cur;
        state[b++] = {nd, ns};
      }
    }
  }
  string ans_str;
  pair<int, int> st = {0, s};
  while (st != pair<int, int>(0, 0)) {
    ans_str += ans[st.first][st.second];
    st = from[st.first][st.second];
  }
  reverse(ans_str.begin(), ans_str.end());
  cout << (!vis[0][s] ? "-1" : ans_str) << '\n';
  return 0;
}