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>
struct r {
  int d, s;
} q[2500050], g[505][5050];
int d, s, h, t;
bool v[505][5050];
void print(int x, int y) {
  if (y == s) return;
  print(g[x][y].d, y + g[x][y].s);
  printf("%d", g[x][y].s);
}
int main() {
  scanf("%d%d", &d, &s);
  h = 1;
  for (int i = 1; i <= 9 && i <= s; i++)
    q[++t] = (r){i % d, s - i}, g[i % d][s - i] = (r){0, i},
    v[i % d][s - i] = 1;
  while (h <= t) {
    r now = q[h++];
    if (!now.d && !now.s) {
      print(0, 0);
      return 0;
    }
    for (int i = 0; i <= 9 && i <= now.s; i++) {
      int x = (now.d * 10 + i) % d, y = now.s - i;
      if (!v[x][y]) v[x][y] = 1, q[++t] = (r){x, y}, g[x][y] = (r){now.d, i};
    }
  }
  printf("-1\n");
}