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;
int d, s;
int dp[10][500][5005];
int solve(int dig, int rem, int sum) {
  if (sum < 0) return 0;
  if (rem == 0 && sum == 0) return dp[dig][rem][sum] = 1;
  int &ret = dp[dig][rem][sum];
  if (ret != -1) return ret;
  ret = 0;
  int here = INT_MAX;
  for (int i = 9; i >= 0; --i) {
    int now = solve(i, (rem * 10 + i) % d, sum - i);
    if (now) here = min(here, now + 1);
  }
  if (here == INT_MAX) here = 0;
  return ret = here;
}
void getRes(int dig, int rem, int sum, string &res) {
  int here = dp[dig][rem][sum];
  for (int i = 0; i < 10; i++) {
    if (dp[i][(rem * 10 + i) % d][sum - i] &&
        dp[i][(rem * 10 + i) % d][sum - i] == here - 1) {
      res += i + '0';
      getRes(i, (rem * 10 + i) % d, sum - i, res);
      return;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> d >> s;
  memset(dp, -1, sizeof(dp));
  if (solve(0, 0, s)) {
    string res;
    getRes(0, 0, s, res);
    cout << res << "\n";
  } else
    cout << "-1\n";
  return 0;
}