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;
struct node {
  int ret, sum;
  string path;
};
bool vis[600][5010];
queue<node> Q;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  node a;
  a.ret = 0, a.sum = 0;
  Q.push(a);
  vis[0][0] = true;
  while (!Q.empty()) {
    node current = Q.front();
    Q.pop();
    if (current.ret == 0 && current.sum == m) {
      cout << current.path << endl;
      return 0;
    }
    if (current.sum > m) {
      continue;
    }
    for (int i = 0; i <= 9; i++) {
      node nw;
      nw.ret = (current.ret * 10 + i) % n;
      nw.sum = current.sum + i;
      if (vis[nw.ret][nw.sum]) continue;
      vis[nw.ret][nw.sum] = true;
      char now = '0' + i;
      nw.path = current.path + now;
      Q.push(nw);
    }
  }
  printf("-1\n");
  return 0;
}