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;
inline int setBit(int N, int pos) { return N = N | (1 << pos); }
inline int resetBit(int N, int pos) { return N = N & ~(1 << pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1 << pos)); }
const int inf = 1e9;
struct edgeData {
  pair<short, short> v;
  char digit;
};
pair<short, short> revV[510][5010][11];
char revDigit[510][5010][11];
int key[510][5010];
int d, s;
pair<int, int> dist[510][5010];
edgeData par[510][5010];
struct data {
  pair<int, int> u;
  pair<int, int> cost;
};
priority_queue<data> Q;
bool operator<(data a, data b) { return a.cost > b.cost; }
bool dijkstra(pair<int, int> source, pair<int, int> dest) {
  for (int i = 0; i < d; i++) {
    for (int j = 0; j <= s; j++) {
      dist[i][j] = {inf, inf};
    }
  }
  dist[source.first][source.second] = {0, 0};
  Q.push({source, dist[source.first][source.second]});
  while (!Q.empty()) {
    pair<int, int> u = Q.top().u;
    pair<int, int> c = Q.top().cost;
    Q.pop();
    if (u == dest) return true;
    if (dist[u.first][u.second] != c) continue;
    for (int i = 0; i < key[u.first][u.second]; i++) {
      edgeData nxt = {revV[u.first][u.second][i],
                      revDigit[u.first][u.second][i]};
      pair<int, int> nw = c;
      nw.first++;
      nw.second = nxt.digit;
      if (dist[nxt.v.first][nxt.v.second] > nw) {
        dist[nxt.v.first][nxt.v.second] = nw;
        par[nxt.v.first][nxt.v.second] = {u, nxt.digit};
        Q.push({nxt.v, nw});
      }
    }
  }
  return false;
}
void go(pair<int, int> me, pair<int, int> dest) {
  if (me == dest) return;
  printf("%d", par[me.first][me.second].digit);
  go(par[me.first][me.second].v, dest);
}
int main() {
  scanf("%d %d", &d, &s);
  for (int i = 0; i < d; i++) {
    for (int j = 0; j <= s; j++) {
      pair<int, int> u = {i, j};
      for (int k = 0; k < 10; k++) {
        if (j + k > s) break;
        pair<int, int> v = {(i * 10 + k) % d, j + k};
        int nw = key[v.first][v.second]++;
        revV[v.first][v.second][nw] = u;
        revDigit[v.first][v.second][nw] = k;
      }
    }
  }
  pair<int, int> dest = {0, s};
  pair<int, int> source = {0, 0};
  if (!dijkstra(dest, source))
    puts("-1");
  else
    go(source, dest), puts("");
  return 0;
}