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;
struct entry {
  int prevs;
  int prevd;
  int digit;
};
entry dp[5001][500];
void printNum(int s, int d) {
  if (dp[s][d].prevs != -1) {
    printNum(dp[s][d].prevs, dp[s][d].prevd);
  }
  cout << dp[s][d].digit;
}
int main() {
  cin >> d >> s;
  for (int i = 0; i <= s; i++) {
    for (int j = 0; j < d; j++) {
      dp[i][j] = {-1, -1, -1};
    }
  }
  queue<pair<int, int>> q;
  for (int digit = 0; digit <= 9; digit++) {
    int rem = digit % d;
    if (dp[digit][rem].digit != -1) continue;
    dp[digit][rem] = {-1, -1, digit};
    if (digit != 0) q.push({digit, rem});
  }
  while (q.size() > 0) {
    auto p = q.front();
    q.pop();
    int sum = p.first, rem = p.second;
    for (int digit = 0; digit < 10; digit++) {
      int ns = sum + digit;
      if (ns > s) continue;
      int nr = (rem * 10 + digit) % d;
      if (dp[ns][nr].digit != -1) continue;
      dp[ns][nr] = {sum, rem, digit};
      q.push({ns, nr});
    }
  }
  printNum(s, 0);
}