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 = 610;
const int MAXR = 505;
bitset<MAXR> f[MAXN][5010];
int D, S, pw[MAXN];
void dfs(int x, int s, int r, bool fir) {
  if (x == 0) return;
  for (int i = fir; i <= 9; i++)
    if (f[x - 1][s - i][(r - pw[x - 1] * i % D + D) % D])
      return putchar('0' + i),
             dfs(x - 1, s - i, (r - pw[x - 1] * i % D + D) % D, 0);
}
int main() {
  scanf("%d%d", &D, &S);
  pw[0] = 1;
  int lim = max(S / 9 + 5, 500);
  f[0][0][0] = 1;
  for (int i = 1; i <= lim; i++) pw[i] = pw[i - 1] * 10 % D;
  for (int i = 1; i <= lim; i++) {
    for (int j = 0; j <= S; j++)
      for (int k = 0; k <= min(9, j); k++)
        f[i][j] |= f[i - 1][j - k] << (k * pw[i - 1] % D) |
                   f[i - 1][j - k] >> (D - k * pw[i - 1] % D);
    if (f[i][S][0]) return dfs(i, S, 0, 1), puts(""), 0;
  }
  puts("-1");
}