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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const long long INF = 1e18;
const long double EPS = 1e-12;
int d, s;
bool vis[5105][515];
int pa[5105][515];
int parem[5105][515];
vector<int> ans;
vector<pair<int, vector<int> > > fin;
void go(int sum, int rem, int dig, int len) {
  if (len == 0) {
    reverse(ans.begin(), ans.end());
    fin.push_back(make_pair(ans.size(), ans));
    return;
  }
  ans.push_back(dig);
  int dd = pa[sum][rem];
  int remm = parem[sum][rem];
  go(sum - dig, remm, dd, len - 1);
}
queue<vector<int> > qu;
void solve(int dii) {
  while (not qu.empty()) qu.pop();
  vis[dii][dii % d] = 1;
  qu.push({dii, dii % d, dii, 0});
  while (not qu.empty()) {
    auto vec = qu.front();
    qu.pop();
    int sum = vec[0], rem = vec[1], dig = vec[2], len = vec[3];
    if (sum > s) continue;
    if (sum > 5001) continue;
    if (len > 50001) continue;
    for (int i = 0; i <= 9; i++) {
      if (sum == 0 && i == 0) continue;
      int sumi = sum + i;
      int remi = (rem * 10 + i) % d;
      if (not vis[sumi][remi]) {
        pa[sumi][remi] = dig;
        parem[sumi][remi] = rem;
        vis[sumi][remi] = 1;
        qu.push({sumi, remi, i, len + 1});
      }
      if (sumi == s && remi == 0) {
        ans.clear();
        go(sumi, remi, i, len + 1);
        return;
      }
    }
  }
}
int main() {
  scanf("%d%d", &d, &s);
  vis[0][0] = 1;
  solve(0);
  if (not fin.empty()) {
    sort(fin.begin(), fin.end());
    for (int i = 0; i < fin[0].first; i++) {
      printf("%d", fin[0].second[i]);
    }
    printf("\n");
    return 0;
  }
  cout << "-1" << endl;
  return 0;
}