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;
struct Nodo {
  int d, s;
  string out;
};
long long int visto[501][5001];
void bfs(int d, int s) {
  queue<Nodo> cola;
  cola.push(Nodo{0, 0, ""});
  visto[0][0] = 1;
  while (cola.empty() == false) {
    Nodo nodo_aux = cola.front();
    cola.pop();
    if (nodo_aux.s > s) continue;
    if (nodo_aux.d == 0 and nodo_aux.s == s) {
      cout << nodo_aux.out;
      return;
    } else {
      for (int i = 0; i < 10; i++) {
        int S = nodo_aux.s + i;
        int D = (nodo_aux.d * 10 + i) % d;
        if (!visto[D][S]) {
          visto[D][S] = 1;
          cola.push(Nodo{D, S, nodo_aux.out + char(i + '0')});
        }
      }
    }
  }
  cout << -1;
  return;
}
int main() {
  int d, s;
  cin >> d >> s;
  bfs(d, s);
}