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 = 510, S = 5100;
int dis[N][S];
int n, s;
int father_t[N][S];
vector<int> num;
pair<int, int> father[N][S];
const int inf = 1e9;
const int D = 10;
queue<pair<int, int> > pq;
void bfs() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < S; j++) {
      dis[i][j] = inf;
    }
  }
  for (int d = 1; d < D; d++) {
    pq.push({d % n, d});
    dis[d % n][d] = 0;
  }
  vector<pair<int, pair<int, int> > > layer_tmp;
  while (!pq.empty()) {
    pair<int, int> u = pq.front();
    pq.pop();
    for (int d = 0; d < D; d++) {
      int nxt = (u.first * 10 + d) % n;
      int sum = (u.second + d);
      if (sum >= S) {
        break;
      }
      if (dis[nxt][sum] > dis[u.first][u.second] + 1) {
        father[nxt][sum] = {u.first, u.second};
        father_t[nxt][sum] = d;
        dis[nxt][sum] = dis[u.first][u.second] + 1;
        pq.push({nxt, sum});
      }
    }
  }
}
void print() {
  if (dis[0][s] != inf) {
    pair<int, int> cur = {0, s};
    for (int sz = dis[0][s]; sz > 0; sz--) {
      num.push_back(father_t[cur.first][cur.second]);
      cur = father[cur.first][cur.second];
    }
    num.push_back(cur.second);
    reverse(num.begin(), num.end());
    for (int i = 0; i < num.size(); i++) {
      printf("%d", num[i]);
    }
    printf("\n");
  } else {
    printf("-1\n");
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  scanf("%d %d", &n, &s);
  bfs();
  print();
  return 0;
}