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 read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch <= '9' && ch >= '0') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
struct edge {
  int m, ss;
  string a;
};
queue<edge> q;
int have[500 + 10][5000 + 10];
int main() {
  int d = read(), s = read();
  q.push((edge){0, 0, ""});
  have[0][0] = 1;
  bool found_answer = 0;
  while (!q.empty()) {
    int sum = q.front().ss;
    int mod = q.front().m;
    string ans = q.front().a;
    q.pop();
    if (sum > s) continue;
    if (mod == 0 && sum == s) {
      cout << ans << endl;
      found_answer = 1;
      return 0;
    }
    for (int i = 0; i < 10; i++) {
      int x = (mod * 10 + i) % d;
      int y = sum + i;
      if (!have[x][y]) {
        have[x][y] = 1;
        q.push((edge){x, y, ans + (char)(i + 48)});
      }
    }
  }
  if (!found_answer) puts("-1");
  return 0;
}