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;
int dis[505][5005];
tuple<int, int, int> from[505][5005];
int d, s;
void bfs() {
  queue<pair<int, int> > q;
  q.emplace(0, 0);
  memset(dis, 0x3F, sizeof dis);
  dis[0][0] = 0;
  while (!q.empty()) {
    pair<int, int> cur = q.front();
    q.pop();
    int mod, sum;
    tie(mod, sum) = cur;
    if (mod == 0 && sum == s) {
      string ans = "";
      int D = dis[mod][sum];
      for (int i = int(0); i < int(D); i++) {
        int prev_mod, prev_sum, prev_digit;
        tie(prev_mod, prev_sum, prev_digit) = from[mod][sum];
        ans += prev_digit + '0';
        mod = prev_mod;
        sum = prev_sum;
      }
      reverse(ans.begin(), ans.end());
      cout << ans << '\n';
      exit(0);
    }
    for (int i = int(0); i < int(10); i++) {
      int new_mod = (mod * 10 + i) % d;
      int new_sum = sum + i;
      if (new_sum <= s && dis[new_mod][new_sum] > dis[mod][sum] + 1) {
        dis[new_mod][new_sum] = dis[mod][sum] + 1;
        q.emplace(new_mod, new_sum);
        from[new_mod][new_sum] = tuple<int, int, int>(mod, sum, i);
      }
    }
  }
}
int main() {
  scanf("%d %d", &d, &s);
  bfs();
  puts("-1");
  return 0;
}