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 INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int D = 512, S = 5123;
int d, s;
int dist[D][S];
tuple<int, int, int> pai[D][S];
void bfs() {
  memset(dist, INF, sizeof dist);
  queue<pair<int, int> > q;
  q.emplace(0, 0);
  while (q.size()) {
    int a = q.front().first, b = q.front().second;
    q.pop();
    for (int i = 0; i <= 9; i++) {
      if (!b and !i) continue;
      int na = (a * 10 + i) % d;
      int nb = b + i;
      if (nb <= s and dist[na][nb] == INF) {
        dist[na][nb] = dist[a][b] + 1;
        pai[na][nb] = make_tuple(a, b, i);
        q.emplace(na, nb);
      }
    }
  }
  if (dist[0][s] == INF) {
    printf("-1\n");
    exit(0);
  }
  vector<int> ans;
  int a = 0, b = s;
  while (a or b) {
    int aa, bb, i;
    tie(aa, bb, i) = pai[a][b];
    ans.push_back(i);
    a = aa;
    b = bb;
  }
  reverse(ans.begin(), ans.end());
  for (auto it : ans) printf("%d", it);
  printf("\n");
}
int main(void) {
  scanf("%d %d", &d, &s);
  bfs();
  return 0;
}