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>
#pragma GCC optimize(2)
using namespace std;
template <class T>
inline void in(T &x) {
  x = 0;
  bool f = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
  if (f) x = -x;
}
bitset<500> b[5000 / 9 + 11][5001];
int d, s;
int ten[5000 / 9 + 11];
const int maxn = 5000 / 9 + 10;
void dfs(int wei, int sd, int res) {
  if (wei == 0) exit(0);
  for (register int i = 0, t; i <= 9; ++i) {
    t = (res - (long long)i * ten[wei - 1] % d + d) % d;
    if (b[wei - 1][sd - i][t]) {
      putchar('0' + i);
      dfs(wei - 1, sd - i, t);
      return;
    }
  }
}
signed main() {
  in(d), in(s);
  ten[0] = 1;
  for (register int i = 1; i <= maxn; ++i)
    ten[i] = (long long)ten[i - 1] * 10 % d;
  b[0][0][0] = 1;
  for (register int i = 1, t; i <= maxn; ++i) {
    for (register int j = 0, mj = min(s, 9 * i); j <= mj; ++j) {
      for (register int k = 0; k <= 9 && k <= j; ++k) {
        t = (long long)ten[i - 1] * k % d;
        b[i][j] |= b[i - 1][j - k] << t;
        b[i][j] |= b[i - 1][j - k] >> (d - t);
      }
    }
    if (b[i][s][0]) {
      dfs(i, s, 0);
    }
  }
  puts("-1");
  return 0;
}