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 D = 505;
const int N = 5005;
pair<int, int> pre[D][N];
int ans[D][N];
void solve() {
  memset(pre, -1, sizeof(pre));
  memset(ans, -1, sizeof(ans));
  int d, s;
  cin >> d >> s;
  queue<pair<int, int> > que;
  que.push(pair<int, int>(0, 0));
  vector<int> vec;
  while (!que.empty()) {
    pair<int, int> u = que.front();
    que.pop();
    if (u.first == 0 && u.second == s) {
      pair<int, int> cur = u;
      while (!(cur.first == 0 && cur.second == 0)) {
        vec.push_back(ans[cur.first][cur.second]);
        cur = pre[cur.first][cur.second];
      }
      break;
    }
    for (int i = 0; i <= 9; i++) {
      pair<int, int> v = pair<int, int>((u.first * 10 + i) % d, u.second + i);
      if (v.second <= s && ans[v.first][v.second] == -1) {
        ans[v.first][v.second] = i;
        pre[v.first][v.second] = u;
        que.push(v);
      }
    }
  }
  if (!vec.size())
    printf("-1\n");
  else {
    reverse(vec.begin(), vec.end());
    for (auto i : vec) putchar(i + '0');
    printf("\n");
  }
}
int main() {
  solve();
  return 0;
}