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;
struct record {
  int reminder, least;
  char dig;
  record() : dig(0) {}
  record(int r, int l, char d) : reminder(r), least(l), dig(d) {}
};
int d, s;
bool exist[505][5005];
record Record[505][5005];
queue<pair<int, int> > Q;
void getNum(int nRem, int nSum);
int main() {
  scanf("%d %d", &d, &s);
  memset(exist, false, sizeof exist);
  exist[0][0] = true;
  while (!Q.empty()) Q.pop();
  Q.push(make_pair(0, 0));
  pair<int, int> now;
  while (!Q.empty()) {
    now = Q.front();
    Q.pop();
    for (register int i = 0; i < 10; i++) {
      int nRem = (now.first * 10 + i) % d;
      int nSum = now.second + i;
      if (nSum > s) break;
      if (!exist[nRem][nSum]) {
        Record[nRem][nSum] = record(now.first, now.second, i + '0');
        exist[nRem][nSum] = true;
        Q.push(make_pair(nRem, nSum));
      }
    }
  }
  if (exist[0][s]) {
    getNum(0, s);
    printf("\n");
  } else
    printf("-1\n");
  return 0;
}
void getNum(int nRem, int nSum) {
  if (Record[nRem][nSum].dig != 0) {
    getNum(Record[nRem][nSum].reminder, Record[nRem][nSum].least);
    printf("%c", Record[nRem][nSum].dig);
  }
}