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 d, s, cost[5100][550];
pair<char, pair<int, int> > par[5100][550];
const int oo = 1e9;
queue<pair<int, int> > q;
int main() {
  memset(cost, -1, sizeof cost);
  cin >> d >> s;
  q.push(make_pair(0, 0));
  cost[0][0] = 0;
  while (q.size()) {
    pair<int, int> src = q.front();
    q.pop();
    if (src.first > s) continue;
    if (src.first == s && src.second == 0) {
      string fn = "";
      pair<int, int> cur = src;
      while (cur != make_pair(0, 0)) {
        fn += par[cur.first][cur.second].first;
        cur = par[cur.first][cur.second].second;
      }
      reverse(fn.begin(), fn.end());
      cout << fn << endl;
      return 0;
    }
    for (int i = 0; i <= 9; ++i) {
      pair<int, int> nw = make_pair(src.first + i, (src.second * 10 + i) % d);
      if (cost[nw.first][nw.second] == -1) {
        cost[nw.first][nw.second] = cost[src.first][src.second] + 1;
        par[nw.first][nw.second] = make_pair(i + '0', src);
        q.push(nw);
      }
    }
  }
  puts("-1");
  return 0;
}