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 int Pow(long long int a, long long int b, long long int md) {
  if (b == 0) return 1;
  if (b & 1) return a * Pow(a * a % md, b / 2, md) % md;
  return Pow(a * a % md, b / 2, md) % md;
}
const long long int MAXN = 5e3 + 10;
const long long int INF = 8e18;
const long long int MOD = 1e9 + 7;
long long int dist[MAXN / 10][MAXN], D, Sr;
pair<long long int, long long int> par[MAXN / 10][MAXN];
void BFS(long long int i = 0, long long int j = 0) {
  memset(dist, 63, sizeof dist);
  dist[0][0] = 0;
  queue<pair<long long int, long long int> > Q;
  Q.emplace(0, 0);
  while ((long long int)Q.size()) {
    tie(i, j) = Q.front();
    Q.pop();
    for (long long int k = 0; k < 10; k++) {
      long long int x = (i * 10 + k) % D, y = j + k;
      if (y >= MAXN) continue;
      if (dist[x][y] > dist[i][j] + 1) {
        dist[x][y] = dist[i][j] + 1;
        par[x][y] = {i, k};
        Q.emplace(x, y);
      }
    }
  };
}
void Print() {
  long long int x = 0, y = Sr;
  vector<long long int> ans;
  while (x != 0 || y != 0) {
    ans.push_back(par[x][y].second);
    long long int X = par[x][y].second;
    x = par[x][y].first, y -= X;
  }
  reverse((ans).begin(), (ans).end());
  for (long long int X : ans) printf("%lld", X);
  printf("\n");
}
int main() {
  scanf("%lld%lld", &D, &Sr);
  BFS();
  if (dist[0][Sr] > INF / 10) return !printf("-1\n");
  Print();
  return 0;
}