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 int const mod = 1000000006;
long long int power(long long int x, long long int y) {
  long long int temp;
  if (y == 0) return 1;
  temp = power(x, y / 2) % (mod + 1);
  if (y % 2 == 0)
    return ((temp % (mod + 1)) * (temp % (mod + 1))) % (mod + 1);
  else
    return (((x) % (mod + 1)) * ((temp * temp) % (mod + 1))) % (mod + 1);
}
long long int gcd1(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd1(b % a, a);
}
long long int lcm(long long int a, long long int b) {
  return (a * b) / gcd1(a, b);
}
struct tt {
  long long int sum;
  string vec;
  long long int rem;
};
bool funsort(pair<long long int, long long int> a,
             pair<long long int, long long int> b) {
  if (a.first != b.first) {
    return a.first < b.first;
  } else {
    return a.second > b.second;
  }
}
int dp[500][5019];
int main() {
  cin.tie(NULL);
  cout.tie(NULL);
  long long int s, d;
  cin >> d >> s;
  tt temp;
  temp.rem = 0;
  temp.sum = 0;
  queue<tt> Q;
  dp[0][0] = 1;
  Q.push(temp);
  while (!Q.empty()) {
    temp = Q.front();
    Q.pop();
    if (temp.sum == s && temp.rem == 0) {
      for (int i = 0; i < (int)temp.vec.length(); i++) cout << temp.vec[i];
      return 0;
    }
    long long int osum = temp.sum;
    long long int orem = temp.rem;
    long long int olen = temp.vec.length();
    for (int i = 0; i < (int)10; i++) {
      long long int rem;
      rem = temp.rem;
      rem *= 10;
      rem += i;
      rem %= d;
      long long int sum = temp.sum + i;
      if (sum > s) {
        break;
      }
      if (sum == s && rem == 0) {
        temp.vec.push_back((char)i + 48);
        for (int i = 0; i < (int)temp.vec.length(); i++) cout << temp.vec[i];
        return 0;
      }
      if (dp[rem][sum] == 0) {
        dp[rem][sum] = 1;
        temp.rem = rem;
        temp.sum = sum;
        temp.vec.push_back((char)i + 48);
        Q.push(temp);
        temp.vec.pop_back();
        temp.sum = osum;
        temp.rem = orem;
      }
    }
  }
  cout << -1;
}