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 ms = 5100;
const int me = 510;
const int sigma = 30;
int n, d, mod, qt;
int vis[me][ms];
char ans[me][ms];
pair<int, int> prev_state[me][ms];
void bfs() {
  queue<pair<int, int> > fila;
  fila.push({0, 0});
  memset(vis, 0, sizeof(vis));
  vis[0][0] = 1;
  prev_state[0][0] = {-1, -1};
  while (!fila.empty()) {
    int number = fila.front().first;
    int digits = fila.front().second;
    fila.pop();
    if (number == 0 && digits == qt) break;
    if (digits > qt) continue;
    for (int i = (digits == 0 ? 1 : 0); i <= 9; i++) {
      int cur_n = ((10 * number) + i) % mod;
      int qt_n = digits + i;
      if (qt_n <= qt && vis[cur_n][qt_n] == 0) {
        fila.push({cur_n, qt_n});
        ans[cur_n][qt_n] = (char)'0' + i;
        prev_state[cur_n][qt_n] = {number, digits};
        vis[cur_n][qt_n] = 1;
      }
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> mod >> qt;
  bfs();
  if (vis[0][qt] == 1) {
    pair<int, int> state = {0, qt};
    string total = "";
    while (state.first != -1 && ans[state.first][state.second] != 0) {
      total += ans[state.first][state.second];
      state = prev_state[state.first][state.second];
    }
    reverse(total.begin(), total.end());
    cout << total << '\n';
  } else {
    cout << -1 << '\n';
  }
}