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;
using ll = long long;
using ii = pair<int, int>;
const int N = 100005;
pair<ii, int> pai[5005][503];
int main() {
  memset(pai, -1, sizeof pai);
  int d, s;
  scanf("%d %d", &d, &s);
  queue<ii> q;
  for (int i = 1; i < 10; i++) {
    q.push({i, i % d});
    pai[i][i % d] = {{0, 0}, i};
  }
  ii ans = {-1, -1};
  int sum, rt;
  while (!q.empty()) {
    tie(sum, rt) = q.front();
    q.pop();
    if (sum > s) continue;
    if (sum == s && rt == 0) {
      ans = {sum, rt};
      break;
    }
    for (int i = 0; i < 10; i++)
      if (sum + i <= s) {
        if (pai[sum + i][(rt * 10 + i) % d].second == -1) {
          q.push({sum + i, (rt * 10 + i) % d});
          pai[sum + i][(rt * 10 + i) % d] = {{sum, rt}, i};
        }
      }
  }
  if (ans.first == -1) {
    printf("-1\n");
  } else {
    vector<int> ansv;
    while (ans.first != 0) {
      ansv.push_back(pai[ans.first][ans.second].second);
      ans = pai[ans.first][ans.second].first;
    }
    reverse(ansv.begin(), ansv.end());
    for (int i : ansv) {
      printf("%d", i);
    }
    printf("\n");
  }
  return 0;
}