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 inf = 0x3f3f3f3f;
const int maxn = 505;
int readint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m;
bool vis[5020][maxn];
int d, s;
struct Node {
  int d, s;
  string ans;
  Node(int _d, int _s, string _ans) : d(_d), s(_s), ans(_ans) {}
};
void solve() {
  queue<Node> q;
  while (!q.empty()) q.pop();
  q.push(Node(0, 0, ""));
  vis[0][0] = true;
  while (!q.empty()) {
    Node temp = q.front();
    q.pop();
    if (temp.d == 0 && temp.s == s) {
      cout << temp.ans << endl;
      return;
    }
    if (temp.s > s) continue;
    int dd;
    for (int i = 0; i < 10; i++) {
      dd = (temp.d * 10 + i) % d;
      if (!vis[temp.s + i][dd] && temp.s + i <= s) {
        q.push(Node(dd, temp.s + i, temp.ans + char(i + '0')));
        vis[temp.s + i][dd] = true;
      }
    }
  }
  cout << -1 << endl;
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> d >> s;
  solve();
  return 0;
}