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;
bool cx[501][5001];
struct data {
  int sd;
  int sum;
  string z;
};
data check;
int main() {
  cin >> d >> s;
  queue<data> q;
  memset(cx, true, sizeof(cx));
  for (int i = 1; i <= 9; i++) {
    int x = i;
    ostringstream convert;
    convert << i;
    check.sd = i % d;
    check.sum = x;
    check.z = convert.str();
    if (check.sd == 0 && check.sum == s) {
      cout << check.sum;
      exit(0);
    } else
      q.push(check);
  }
  while (!q.empty()) {
    data check2 = q.front();
    q.pop();
    for (int i = 0; i <= 9; i++) {
      check.sd = (10 * check2.sd + i) % d;
      check.sum = check2.sum + i;
      if (check.sd == 0 && check.sum == s) {
        ostringstream convert;
        convert << i;
        check.z = check2.z + convert.str();
        cout << check.z;
        exit(0);
      } else {
        if (cx[check.sd][check.sum] && check.sum <= s) {
          cx[check.sd][check.sum] = false;
          ostringstream convert;
          convert << i;
          check.z = check2.z + convert.str();
          q.push(check);
        }
      }
    }
  }
  cout << -1;
  return 0;
}