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 MAX = 5000 + 10;
const int MOD = 1e9 + 7;
bool vis[MAX][MAX];
bool dp[MAX][MAX];
int Dist[MAX][MAX];
int d, s;
void solve() {
  for (int i = 0; i < MAX; i++) {
    for (int j = 0; j < MAX; j++) Dist[i][j] = 1e9;
  }
  queue<pair<int, int> > Q;
  Q.push({0, 0});
  vis[0][0] = 1;
  Dist[0][0] = 0;
  while (!Q.empty()) {
    auto top = Q.front();
    Q.pop();
    for (int i = 0; i < 10; i++) {
      int rem = (top.first * 10 + i) % d;
      int sum = top.second + i;
      if (sum > s || vis[rem][sum]) continue;
      vis[rem][sum] = 1;
      Dist[rem][sum] = 1 + Dist[top.first][top.second];
      Q.push({rem, sum});
    }
  }
}
char to_char(int x) { return (char)(48 + x); }
string A = "";
void PrintPath(int rem, int sum) {
  if (rem == 0 && sum == s) {
    cout << A << endl;
    exit(0);
  }
  if (dp[rem][sum]) return;
  dp[rem][sum] = 1;
  for (int i = 0; i < 10; i++) {
    int rem2 = (rem * 10 + i) % d;
    int sum2 = sum + i;
    if (sum2 > s) continue;
    if (Dist[rem2][sum2] == 1 + Dist[rem][sum]) {
      A += to_char(i);
      PrintPath(rem2, sum2);
      A.pop_back();
    }
  }
}
int main() {
  cin >> d >> s;
  solve();
  if (Dist[0][s] == 1e9) {
    cout << -1;
    return 0;
  }
  PrintPath(0, 0);
  return 0;
}