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;
int visit[610][6100];
int d, s;
int qd[5000010], qs[5000010];
int digit[5000010], last[5000010];
int res[1000000];
void bfs() {
  qd[1] = 0;
  qs[1] = 0;
  visit[0][0] = 1;
  int h = 0, t = 1, nowd, nows, newd, news;
  for (; h < t;) {
    nowd = qd[++h];
    nows = qs[h];
    for (int i = 0; i < 10; i++) {
      newd = nowd * 10 + i;
      newd %= d;
      news = nows + i;
      if (news > s) continue;
      if (visit[newd][news]) continue;
      visit[newd][news] = ++t;
      digit[t] = i;
      last[t] = h;
      qd[t] = newd;
      qs[t] = news;
    }
  }
}
int main() {
  scanf("%d%d", &d, &s);
  bfs();
  int p = visit[0][s], cnt = 0;
  if (p == 0)
    printf("-1\n");
  else {
    for (; p != 1; p = last[p]) res[++cnt] = digit[p];
    for (int i = cnt; i; i--) printf("%d", res[i]);
    printf("\n");
  }
  return 0;
}