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 N = 505, M = 5010;
int v[N][M], f[N][M][3];
void ot(int x, int y) {
  if (x || y) {
    int j;
    int xx, yy;
    xx = f[x][y][0];
    yy = f[x][y][1];
    j = f[x][y][2];
    ot(xx, yy);
    cout << j;
  }
}
int main() {
  ios::sync_with_stdio(false);
  int d, s;
  cin >> d >> s;
  queue<pair<int, int>> q;
  q.push({0, 0});
  while (!q.empty()) {
    pair<int, int> p = q.front();
    int x = p.first;
    int y = p.second;
    q.pop();
    for (int j = 0; j <= 9; j++) {
      int xx = (x * 10 + j) % d;
      int yy = y + j;
      if (yy <= s & (!v[xx][yy])) {
        v[xx][yy] = 1;
        f[xx][yy][0] = x;
        f[xx][yy][1] = y;
        f[xx][yy][2] = j;
        if (xx == 0 && yy == s) {
          q = queue<pair<int, int>>();
          break;
        }
        q.push({xx, yy});
      }
    }
  }
  if (v[0][s])
    ot(0, s);
  else
    cout << -1 << endl;
  return 0;
}