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 main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i, j, k, l, m, n;
  cin >> n >> m;
  int vis[n][m + 1], ch[n][m + 1];
  pair<int, int> par[n][m + 1];
  memset(vis, 0, sizeof vis);
  memset(ch, 0, sizeof ch);
  list<pair<int, int> > q;
  q.push_back({0, 0});
  vis[0][0] = 1;
  string ans = "-1";
  while (!q.empty()) {
    pair<int, int> p1 = q.front();
    q.pop_front();
    if (p1.first == 0 && p1.second == m) {
      ans.clear();
      while (p1.first != 0 || p1.second != 0) {
        ans.push_back('0' + ch[p1.first][p1.second]);
        p1 = par[p1.first][p1.second];
      }
      reverse(ans.begin(), ans.end());
      break;
    }
    for (i = 0; i <= 9; i++) {
      int i1 = (p1.first * 10 + i) % n;
      int j1 = (p1.second + i);
      if (j1 <= m) {
        if (!vis[i1][j1]) {
          vis[i1][j1] = 1;
          ch[i1][j1] = i;
          par[i1][j1] = {p1.first, p1.second};
          q.push_back({i1, j1});
        }
      }
    }
  }
  cout << ans << "\n";
  return 0;
}