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 d, s, f[507][5007];
int des[507][5007] = {0};
pair<int, int> fr[507][5007];
queue<pair<int, int> > q;
void SPFA() {
  memset(f, 0x3f, sizeof(f));
  f[0][0] = 0;
  pair<int, int> tp, tt;
  tp.first = 0;
  tp.second = 0;
  q.push(tp);
  while (!q.empty()) {
    tp = q.front();
    q.pop();
    for (int i = 0; i < 10; i++) {
      tt = tp;
      tt.second += i;
      if (tt.second > s) break;
      tt.first = (tt.first * 10 + i) % d;
      if (f[tp.first][tp.second] + 1 < f[tt.first][tt.second]) {
        f[tt.first][tt.second] = f[tp.first][tp.second] + 1;
        q.push(tt);
        fr[tt.first][tt.second] = tp;
        des[tt.first][tt.second] = i;
      }
    }
  }
  return;
}
void print(int a, int b) {
  if ((!a) && (!b)) return;
  print(fr[a][b].first, fr[a][b].second);
  printf("%d", des[a][b]);
  return;
}
int main() {
  scanf("%d%d", &d, &s);
  SPFA();
  if (f[0][s] != 0x3f3f3f3f)
    print(0, s);
  else
    puts("-1");
  return 0;
}