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;
const int N = 500 + 10;
const int M = 5000 + 10;
struct Node {
  int d, num;
  string s;
};
int k, s;
bool flag;
string ans;
queue<Node> Q;
bool vis[N][M];
string t[10] = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
int main() {
  scanf("%d%d", &k, &s);
  for (int i = 1; i <= 9; i++) {
    vis[i % k][i] = 1;
    Q.push((Node){i % k, i, t[i]});
  }
  while (!Q.empty()) {
    auto x = Q.front();
    Q.pop();
    if (x.num == s && x.d == 0) {
      if (ans == "")
        ans = x.s;
      else
        ans = min(ans, x.s);
      continue;
    }
    for (int i = 0; i < 10; ++i) {
      int r = (x.d * 10 + i) % k;
      int nxt = x.num + i;
      if (nxt > s || vis[r][nxt]) continue;
      Q.push((Node){r, nxt, x.s + t[i]});
      vis[r][nxt] = 1;
    }
  }
  if (ans == "")
    puts("-1");
  else
    cout << ans << endl;
  return 0;
}