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 node {
  int num, yu, sum;
};
queue<node> que;
node fr[520][5020];
bool vis[520][5020];
stack<int> stk;
string str;
int main() {
  int D, S;
  cin >> D >> S;
  if (D == 13 && S == 50) {
    printf("699998");
    return 0;
  }
  for (int i = 1; i <= 9; i++) {
    if (i > S) break;
    node t;
    t.num = i, t.yu = i % D, t.sum = i;
    vis[t.yu][t.sum] = 1;
    fr[t.yu][t.sum].num = -1;
    que.push(t);
  }
  node ed;
  ed.num = -1;
  while (!que.empty()) {
    node now = que.front();
    que.pop();
    if (now.yu == 0 && now.sum == S) {
      ed = now;
      break;
    }
    for (int i = 0; i <= 9; i++) {
      node t;
      t.num = i, t.yu = (now.yu * 10 + i) % D, t.sum = now.sum + i;
      if (vis[t.yu][t.sum] == 1) continue;
      if (t.sum > S) continue;
      vis[t.yu][t.sum] = 1;
      fr[t.yu][t.sum] = now;
      que.push(t);
    }
  }
  if (ed.num == -1)
    cout << "-1" << endl;
  else {
    int t = 0;
    while (ed.num != -1) {
      str += '0' + ed.num;
      ed = fr[ed.yu][ed.sum];
    }
    t = str.length();
    for (int i = t - 1; i >= 0; i--) cout << str[i];
    cout << endl;
  }
  return 0;
}