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 DP[510][5010];
pair<pair<int, int>, int> parent[510][5010];
queue<pair<int, int> > BFS;
int n, m;
vector<int> ans;
int main() {
  scanf("%d%d", &n, &m);
  memset(DP, -1, sizeof DP);
  BFS.push({0, m});
  DP[0][m] = 0;
  while (!BFS.empty()) {
    auto cur = BFS.front();
    BFS.pop();
    if (cur == make_pair(0, 0)) break;
    int awal = 0;
    if (cur.second == m) awal++;
    for (int i = awal; i <= 9; i++) {
      auto next = cur;
      next.first *= 10;
      next.first += i;
      next.first %= n;
      next.second -= i;
      if (next.second < 0) continue;
      if (DP[next.first][next.second] != -1) continue;
      DP[next.first][next.second] = DP[cur.first][cur.second] + 1;
      parent[next.first][next.second] = {cur, i};
      BFS.push(next);
    }
  }
  if (DP[0][0] == -1) {
    puts("-1");
    return 0;
  }
  pair<int, int> cur = make_pair(0, 0);
  while (cur != make_pair(0, m)) {
    ans.push_back(parent[cur.first][cur.second].second);
    cur = parent[cur.first][cur.second].first;
  }
  reverse(ans.begin(), ans.end());
  for (auto data : ans) printf("%d", data);
  puts("");
  return 0;
}