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;
clock_t __START, __END;
double __TOTALTIME;
void _MS() { __START = clock(); }
void _ME() {
  __END = clock();
  __TOTALTIME = (double)(__END - __START) / CLOCKS_PER_SEC;
  cout << "Time: " << __TOTALTIME << " s" << endl;
}
const double E = 2.718281828;
const double PI = acos(-1.0);
const long long INF = (1LL << 60);
const int inf = (1 << 30);
const double ESP = 1e-9;
const int N = (int)1e6 + 10;
struct node {
  int px, py, num;
} dp[5005][505];
bool vis[5005][505];
queue<node> q;
void Init(int mod) {
  for (int i = 1; i <= 9; ++i)
    q.push({i, i % mod, i}), vis[i][i % mod] = 1, dp[i][i % mod] = {-1, -1, i};
  while (!q.empty()) {
    node now = q.front();
    q.pop();
    for (int i = 0; i <= 9; ++i) {
      if (now.px + i <= 5000) {
        if (!vis[now.px + i][(now.py * 10 + i) % mod]) {
          q.push({now.px + i, (now.py * 10 + i) % mod, i});
          vis[now.px + i][(now.py * 10 + i) % mod] = 1;
          dp[now.px + i][(now.py * 10 + i) % mod] = {now.px, now.py, i};
        }
      }
    }
  }
}
int ans[N], cnt;
int main() {
  int n, mod;
  scanf("%d%d", &mod, &n);
  Init(mod);
  if (!vis[n][0])
    printf("-1\n");
  else {
    node now = dp[n][0];
    while (1) {
      ans[++cnt] = now.num;
      if (now.px == -1)
        break;
      else
        now = dp[now.px][now.py];
    }
    for (int i = cnt; i >= 1; --i) printf("%d", ans[i]);
  }
  return 0;
}