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 dp[600][6000];
pair<int, int> pre[600][6000];
int d, s;
string bfs() {
  memset(dp, 0, sizeof(dp));
  queue<pair<int, int> > q;
  for (int i = 1; i < 10; ++i) {
    q.push(make_pair(i % d, i));
    dp[i % d][i] = 1;
    pre[i % d][i] = make_pair(0, 0);
  }
  if (dp[0][s] == 0) {
    while (!q.empty()) {
      pair<int, int> p = q.front();
      q.pop();
      int now_d = p.first;
      int now_s = p.second;
      for (int i = 0; i < 10; ++i) {
        int new_d = (now_d * 10 + i) % d;
        int new_s = (now_s + i);
        if (new_s <= s && dp[new_d][new_s] == 0) {
          dp[new_d][new_s] = 1;
          pre[new_d][new_s] = make_pair(now_d, now_s);
          q.push(make_pair(new_d, new_s));
        }
      }
      if (dp[0][s] > 0) {
        break;
      }
    }
  }
  if (dp[0][s] > 0) {
    int x_d = 0, x_s = s;
    string ans = "";
    while (x_s > 0) {
      pair<int, int> x = pre[x_d][x_s];
      int c = x_s - x.second;
      ans = string(1, c + '0') + ans;
      x_d = x.first;
      x_s = x.second;
    }
    return ans;
  }
  return "";
}
int main() {
  while (cin >> d >> s) {
    string ans = bfs();
    if (ans.size() > 0) {
      cout << ans << endl;
    } else {
      cout << -1 << endl;
    }
  }
}