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 int LIM = 5005 + 1, INF = 1e9;
int k, t, dp[LIM][505];
struct data {
  int x, y, d;
  data() {}
  data(int x, int y, int d) : x(x), y(y), d(d) {}
} pt[LIM][505];
int main() {
  scanf("%d%d", &k, &t);
  for (int s = 0; s <= t; s++)
    for (int r = 0; r < k; r++) dp[s][r] = INF;
  queue<pair<int, int> > q;
  for (int i = 1; i < 10; i++) {
    dp[i][i % k] = 1;
    q.push({i, i % k});
    pt[i][i % k] = data(-1, -1, i);
  }
  dp[0][0] = 0;
  while (!q.empty()) {
    int s = q.front().first;
    int r = q.front().second;
    q.pop();
    for (int d = 0; d < 10; d++) {
      if (s + d > t) continue;
      int nS = s + d;
      int nR = (r * 10 + d) % k;
      if (dp[s][r] + 1 < dp[nS][nR]) {
        dp[nS][nR] = dp[s][r] + 1;
        pt[nS][nR] = data(s, r, d);
        q.push({nS, nR});
      }
    }
  }
  if (dp[t][0] == INF) {
    printf("-1\n");
    return 0;
  }
  int x = t, y = 0;
  vector<int> ans;
  while (1) {
    int nx = pt[x][y].x;
    int ny = pt[x][y].y;
    int d = pt[x][y].d;
    ans.push_back(d);
    x = nx, y = ny;
    if (nx == -1 && ny == -1) break;
  }
  for (int i = (int)ans.size() - 1; i >= 0; i--) printf("%d", ans[i]);
  printf("\n");
  return 0;
}