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;
long long dp[5050][505];
pair<long long, long long> pre[5050][505];
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long d, s;
  cin >> d >> s;
  queue<pair<long long, long long>> q;
  for (long long i = 1; i < 10; i++) {
    dp[i][i % d] = 1;
    q.push({i, i % d});
  }
  while (q.size()) {
    pair<long long, long long> curr = q.front();
    q.pop();
    long long sum = curr.first;
    long long div = curr.second;
    for (long long i = 0; i <= 9; i++) {
      long long curr_sum = sum + i;
      long long curr_div = (div * 10 + i) % d;
      if (curr_sum <= s and !dp[curr_sum][curr_div]) {
        dp[curr_sum][curr_div] = dp[sum][div] + 1;
        q.push({curr_sum, curr_div});
        pre[curr_sum][curr_div] = {sum, div};
      }
    }
  }
  if (!dp[s][0]) {
    cout << -1;
  } else {
    vector<long long> ans;
    long long sum = s, div = 0;
    while (true) {
      if (dp[sum][div] == 1) {
        ans.push_back(sum);
        break;
      } else {
        pair<long long, long long> curr = pre[sum][div];
        ans.push_back(sum - curr.first);
        sum = curr.first;
        div = curr.second;
      }
    }
    reverse(ans.begin(), ans.end());
    for (auto x : ans) {
      cout << x;
    }
  }
}