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 Maxn = 5015;
const int Maxm = 505;
const int Inf = 1000000000;
int s, d;
vector<pair<int, int> > toup[Maxm];
int has[Maxn][Maxm];
int main() {
  scanf("%d %d", &d, &s);
  for (int i = 0; i < d; i++)
    for (int j = 0; j < 10; j++) {
      int nw = (10 * i + j) % d;
      toup[nw].push_back(pair<int, int>(i, j));
    }
  fill((int*)has, (int*)has + Maxn * Maxm, Inf);
  has[0][0] = 0;
  priority_queue<pair<int, pair<int, int> > > Q;
  Q.push(pair<int, pair<int, int> >(0, pair<int, int>(0, 0)));
  while (!Q.empty()) {
    pair<int, int> v = Q.top().second;
    int d = -Q.top().first;
    Q.pop();
    if (has[v.first][v.second] != d) continue;
    for (int i = 0; i < toup[v.second].size(); i++) {
      pair<int, int> u = toup[v.second][i];
      pair<int, int> nxt = pair<int, int>(v.first + u.second, u.first);
      if (nxt.first <= s && d + 1 < has[nxt.first][nxt.second]) {
        has[nxt.first][nxt.second] = d + 1;
        Q.push(pair<int, pair<int, int> >(-has[nxt.first][nxt.second], nxt));
      }
    }
  }
  if (has[s][0] >= Inf) {
    printf("-1\n");
    return 0;
  }
  int a = s, b = 0;
  while (has[a][b] > 0) {
    int my = has[a][b];
    for (int i = 0;; i++)
      if (has[a - i][(10 * b + i) % d] == my - 1) {
        printf("%d", i);
        a -= i;
        b = (10 * b + i) % d;
        break;
      }
  }
  printf("\n");
  return 0;
}