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;
const long long MAXN = 5010;
const int MAXD = 510;
pair<int, pair<long long, long long> > vis[MAXD][MAXN];
int D, S;
queue<pair<long long, long long> > Q;
int main() {
  cin >> D >> S;
  for (int i = 0; i < D; ++i)
    for (int j = 0; j <= S; ++j) vis[i][j] = make_pair(-1, make_pair(-1, -1));
  Q.push(make_pair(0, 0));
  while ((long long)Q.size()) {
    int m = Q.front().first;
    int second = Q.front().second;
    Q.pop();
    for (int k = 0; k <= 9; ++k) {
      if (m == 0 && second == 0 && k == 0) continue;
      int new_m = (m * 10 + k) % D;
      int new_s = second + k;
      if (new_s > S) continue;
      if (vis[new_m][new_s].first != -1) continue;
      vis[new_m][new_s] = make_pair(k, make_pair(m, second));
      Q.push(make_pair(new_m, new_s));
    }
  }
  pair<int, pair<long long, long long> > cur = vis[0][S];
  if (cur.first == -1) {
    cout << -1 << '\n';
    return 0;
  }
  vector<long long> ans;
  while (1) {
    if (cur.second.first == 0 & cur.second.second == 0) break;
    ans.emplace_back(cur.first);
    cur = vis[cur.second.first][cur.second.second];
  }
  ans.emplace_back(cur.first);
  reverse(ans.begin(), ans.end());
  for (auto i : ans) cout << i;
}