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 maxc = 5000 + 10;
const int maxn = 500 + 10;
struct Node {
  int u, v;
  Node() {}
  Node(int u, int v) {
    this->u = u;
    this->v = v;
  }
};
bool done[maxn][maxc];
int pre[maxn][maxc];
int num[maxn][maxc];
queue<Node> Q;
int d, s;
inline void Print(int u, int v) {
  if (u == 0 && v == 0) return;
  Print(pre[u][v], v - num[u][v]);
  printf("%d", num[u][v]);
}
signed main() {
  bool tag = false;
  scanf("%d%d", &d, &s);
  Q.push(Node(0, 0));
  done[0][0] = 1;
  while (!Q.empty()) {
    Node x = Q.front();
    Q.pop();
    if (x.u == 0 && x.v == s) {
      tag = 1;
      break;
    }
    for (int i = 0; i <= 9; i++) {
      int tu = (x.u * 10 % d + i) % d, tv = (x.v + i);
      if (tv <= s && !done[tu][tv]) {
        done[tu][tv] = 1;
        pre[tu][tv] = x.u;
        num[tu][tv] = i;
        Q.push(Node(tu, tv));
      }
    }
  }
  if (!tag) return (!printf("-1\n"));
  Print(0, s);
  putchar('\n');
  return 0;
}