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 D = 510;
const int S = 5010;
int _w;
int d, s, f[D][S];
queue<pair<int, int> > q;
void prelude() {
  memset(f, -1, sizeof f);
  f[0][0] = 0;
  q.push(pair<int, int>(0, 0));
  while (!q.empty()) {
    pair<int, int> o = q.front();
    q.pop();
    int a = o.first;
    int b = o.second;
    for (int i = 0; i < 10; ++i) {
      int aa = (a * 10 + i) % d;
      int bb = b + i;
      if (bb < S && f[aa][bb] == -1) {
        f[aa][bb] = f[a][b] + 1;
        q.push(pair<int, int>(aa, bb));
      }
    }
  }
  if (f[0][s] == -1) {
    puts("-1");
    exit(0);
  }
}
int vis[D][S];
int dfs(int a, int b) {
  if (vis[a][b] != -1) return vis[a][b];
  if (!a && b == s) return vis[a][b] = 1;
  vis[a][b] = 0;
  for (int i = 0; i < 10; ++i) {
    int aa = (a * 10 + i) % d;
    int bb = b + i;
    if (bb < S && f[aa][bb] == f[a][b] + 1) vis[a][b] |= dfs(aa, bb);
  }
  return vis[a][b];
}
void answer(int a, int b) {
  if (!a && b == s) return;
  for (int i = 0; i < 10; ++i) {
    int aa = (a * 10 + i) % d;
    int bb = b + i;
    if (bb < S && f[aa][bb] == f[a][b] + 1 && vis[aa][bb]) {
      putchar(i + '0');
      answer(aa, bb);
      return;
    }
  }
}
void solve() {
  memset(vis, -1, sizeof vis);
  dfs(0, 0);
  answer(0, 0);
  puts("");
}
int main() {
  _w = scanf("%d%d", &d, &s);
  prelude(), solve();
  return 0;
}