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 long long INF = 200000000 + 1;
int vis[5005][505];
vector<int> v[5005];
int main() {
  int d, s;
  cin >> d >> s;
  queue<pair<int, int> > q;
  q.push(make_pair(s, 0));
  for (int j = 0; j < d; j++) {
    int u = (j * 10) % d;
    v[u].push_back(j);
  }
  vis[s][0] = 1;
  while (!q.empty()) {
    int sum = q.front().first;
    int md = q.front().second;
    q.pop();
    for (int k = 0; k < 10 && k <= sum; k++) {
      int s1 = sum - k;
      int md1 = (md - k + 10 * d) % d;
      for (int l = 0; l < v[md1].size(); l++) {
        if (vis[s1][v[md1][l]] == 0) {
          q.push(make_pair(s1, v[md1][l]));
          vis[s1][v[md1][l]] = vis[sum][md] + 1;
        }
      }
    }
  }
  if (vis[0][0] == 0) {
    cout << "-1" << '\n';
    return 0;
  }
  int sum = 0;
  int md = 0;
  while (sum <= s) {
    if (sum == s && md == 0) break;
    int l2 = vis[sum][md];
    for (int k = 0; k < 10 && sum + k <= s; k++) {
      int s1 = sum + k;
      int md1 = (md * 10 + k) % d;
      if (vis[s1][md1] + 1 == vis[sum][md] && vis[s1][md1] != 0) {
        cout << k;
        sum = s1;
        md = md1;
        break;
      }
    }
  }
  cout << '\n';
}