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;
string ans;
queue<pair<int, int>> Q;
pair<int, int> parent[5005][505];
int visited[5005][505];
void solve(int d, int s) {
  visited[0][0] = 1;
  Q.push({0, 0});
  while (!Q.empty()) {
    int q = Q.size();
    while (q--) {
      auto pr = Q.front();
      Q.pop();
      int sum = pr.first, mod = pr.second;
      for (int i = 0; i < 10; i++) {
        int new_sum = sum + i;
        int new_mod = (mod * 10 + i) % d;
        if (new_sum > s || visited[new_sum][new_mod]) {
          continue;
        }
        parent[new_sum][new_mod] = make_pair(sum, mod);
        visited[new_sum][new_mod] = visited[sum][mod] + 1;
        Q.push({new_sum, new_mod});
      }
    }
  }
}
int getAns(int d, int s) {
  int x = s, y = 0;
  while (x || y) {
    int next_x = parent[x][y].first;
    int next_y = parent[x][y].second;
    for (int i = 0; i < 10; i++) {
      if (next_x + i == x && (next_y * 10 + i) % d == y) {
        ans.push_back(i + '0');
        break;
      }
    }
    x = next_x, y = next_y;
  }
  reverse(ans.begin(), ans.end());
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  cout.tie(nullptr);
  ;
  int d, s;
  cin >> d >> s;
  solve(d, s);
  if (!visited[s][0]) {
    cout << -1 << endl;
  } else {
    getAns(d, s);
    cout << ans << endl;
  }
}