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;
bool V[510][5010];
pair<int, int> P[510][5010];
char T[510][5010];
char S[510 * 5010];
int d, s;
bool bfs() {
  queue<pair<int, int> > q;
  q.push(make_pair(0, 0));
  V[0][0] = true;
  while (!q.empty()) {
    pair<int, int> aux = q.front();
    q.pop();
    int div = aux.first, sum = aux.second;
    int l = 0;
    if (div == 0 && sum == s) {
      while (div || sum) {
        pair<int, int> prev = P[div][sum];
        S[l++] = T[div][sum];
        div = prev.first;
        sum = prev.second;
      }
      reverse(S, S + l);
      S[l] = '\0';
      return true;
    }
    for (int i = 0; i < 10; i++) {
      int ndiv = (div * 10 + i) % d;
      int nsum = sum + i;
      if (nsum <= s && !V[ndiv][nsum]) {
        q.push(make_pair(ndiv, nsum));
        P[ndiv][nsum] = aux;
        T[ndiv][nsum] = i + '0';
        V[ndiv][nsum] = true;
      }
    }
  }
  return false;
}
int main() {
  scanf("%d %d", &d, &s);
  if (!bfs())
    printf("-1\n");
  else
    printf("%s\n", S);
  return 0;
}