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 maxn = 505 * 5005;
int d, s;
int to[5005][505];
bool vis[5005][505];
vector<int> e;
int getid(int x, int y) {
  if (!x && !y) return 0;
  return x * d + y;
}
struct node {
  int x, y;
  int u;
} p, temp;
queue<node> q;
void bfs() {
  int i, j, k, x, y;
  p.x = s;
  p.y = 0;
  p.u = -1;
  vis[s][0] = 1;
  to[s][0] = -1;
  q.push(p);
  while (!q.empty()) {
    p = q.front();
    q.pop();
    if (p.x == 0 && p.y == 0) return;
    for (i = 0; i < 10; i++) {
      x = p.x - i;
      y = (p.y * 10 + i) % d;
      if (x >= 0) {
        if (!vis[x][y]) {
          temp.x = x;
          temp.y = y;
          temp.u = getid(p.x, p.y);
          q.push(temp);
          to[x][y] = temp.u;
          vis[x][y] = 1;
        }
      }
    }
  }
}
int main() {
  int i, j, k, l, h, x, y, z;
  scanf("%d%d", &d, &s);
  memset(vis, 0, sizeof(vis));
  bfs();
  z = to[0][0];
  h = 0;
  to[s][0] = -1;
  if (vis[0][0] == 0)
    printf("-1\n");
  else {
    while (1) {
      y = (z) % d;
      x = (z - y) / d;
      e.push_back(x - h);
      h = x;
      z = to[x][y];
      if (z == -1) break;
    }
    for (i = e.size() - 1; i >= 0; i--) printf("%d", e[i]);
    printf("\n");
  }
  return 0;
}