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 max = 1e7;
long long inf = 0x7fff;
int dp[1000][5001];
int pi_1[1000][5001];
int pi_2[1000][5001];
int dist[1000][5001];
bool visited[1000][5001];
int dig_sum(int x) { return (x > 0) ? (x % 10) + dig_sum(x / 10) : 0; }
int main() {
  int d, s;
  cin >> d >> s;
  memset(dp, false, sizeof(dp));
  memset(pi_1, false, sizeof(pi_1));
  memset(pi_2, false, sizeof(pi_2));
  memset(dist, false, sizeof(dist));
  memset(visited, false, sizeof(visited));
  queue<tuple<int, int>> todo;
  todo.emplace(0, 0);
  dist[0][0] = 0;
  visited[0][0] = true;
  while (!todo.empty()) {
    auto tup = todo.front();
    todo.pop();
    int frontdigs = get<0>(tup);
    int sum = get<1>(tup);
    for (int i = 9; i >= 0; i--) {
      if (i == 0 && frontdigs == 0) continue;
      int newbigdigs = frontdigs + d * i;
      int newsum = sum + newbigdigs % 10;
      int newdigs = newbigdigs / 10;
      if (newsum <= 5000) {
        if (!visited[newdigs][newsum]) {
          dist[newdigs][newsum] = dist[frontdigs][sum] + 1;
          todo.emplace(newdigs, newsum);
          visited[newdigs][newsum] = true;
          dp[newdigs][newsum] = newbigdigs % 10;
          pi_1[newdigs][newsum] = frontdigs;
          pi_2[newdigs][newsum] = sum;
        } else if (dist[newdigs][newsum] == dist[frontdigs][sum] + 1 &&
                   newbigdigs % 10 < dp[newdigs][newsum]) {
          dp[newdigs][newsum] = newbigdigs % 10;
          pi_1[newdigs][newsum] = frontdigs;
          pi_2[newdigs][newsum] = sum;
        }
      }
    }
  }
  int min_dist = 1e8;
  for (int i = 0; i < 1000; i++) {
    if (dig_sum(i) <= s && visited[i][s - dig_sum(i)]) {
      min_dist = min(min_dist, dist[i][s - dig_sum(i)]);
    }
  }
  if (min_dist == 1e8) {
    cout << "-1" << endl;
    return 0;
  }
  for (int i = 0; i < 1000; i++) {
    if (dig_sum(i) <= s && dist[i][s - dig_sum(i)] == min_dist &&
        visited[i][s - dig_sum(i)]) {
      if (i > 0) cout << i;
      int curdigs = i;
      int cursum = s - dig_sum(i);
      int ctr = 1;
      while (curdigs != 0 || cursum != 0) {
        cout << dp[curdigs][cursum];
        int t_curdigs = pi_1[curdigs][cursum];
        cursum = pi_2[curdigs][cursum];
        curdigs = t_curdigs;
      }
      cout << endl;
      return 0;
    }
  }
}