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;
long long MOD = 1000000007;
long double EPS = 1e-9;
void pre() {}
bool vis[5001][501];
pair<long long, pair<long long, long long> > b[5001][501];
long long d, s;
void bfs() {
  queue<pair<long long, long long> > q;
  q.push({s, 0});
  vis[s][0] = 1;
  while (!q.empty()) {
    pair<long long, long long> tt = q.front();
    q.pop();
    long long second = tt.first;
    long long D = tt.second;
    for (long long i = 0; i < 10; i++) {
      long long newS = second - i;
      long long newD = (D * 10 + i) % d;
      if (newS < 0 || vis[newS][newD]) continue;
      vis[newS][newD] = 1;
      b[newS][newD] = {i, {second, D}};
      q.push({newS, newD});
    }
  }
}
void solve() {
  cin >> d >> s;
  bfs();
  string final = "";
  if (vis[0][0] == 0) {
    cout << -1 << '\n';
    return;
  }
  long long second = 0;
  long long D = 0;
  while (second != s || D != 0) {
    pair<long long, pair<long long, long long> > p = b[second][D];
    final += p.first + '0';
    second = p.second.first;
    D = p.second.second;
  }
  reverse(final.begin(), final.end());
  cout << final << '\n';
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  pre();
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve();
  }
}