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 mod = 1000000007;
const int N = 2e5 + 5;
int d, s;
int dist[505][5005];
pair<int, int> par[505][5005];
int main(int argc, char** argv) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> d >> s;
  memset(dist, -1, sizeof dist);
  queue<pair<int, int>> q;
  for (int i = 0; i < 10; i++) {
    if (dist[i % d][i] == -1) {
      dist[i % d][i] = 1;
      q.push({i % d, i});
      par[i % d][i] = {i, 0};
    }
  }
  while (q.size()) {
    auto cur = q.front();
    q.pop();
    for (int i = 0; i < 10; i++) {
      if (dist[(cur.first * 10 + i) % d][min(5001, cur.second + i)] == -1) {
        dist[(cur.first * 10 + i) % d][min(5001, cur.second + i)] =
            dist[cur.first][cur.second] + 1;
        q.push({(cur.first * 10 + i) % d, min(5001, cur.second + i)});
        par[(cur.first * 10 + i) % d][min(5001, cur.second + i)] = {i,
                                                                    cur.first};
      }
    }
  }
  if (dist[0][s] == -1) {
    cout << -1 << '\n';
    return 0;
  }
  pair<int, int> cur = {0, s};
  string ans = "";
  while (true) {
    int digit = par[cur.first][cur.second].first;
    int to = par[cur.first][cur.second].second;
    ans.push_back('0' + digit);
    cur.second = cur.second - digit;
    cur.first = to;
    if (cur.first == 0 && cur.second == 0) break;
  }
  reverse(begin(ans), end(ans));
  cout << ans << '\n';
  return 0;
}