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;
pair<int, int> M[505][5005];
int vis[505][5005], ok[505][5005];
queue<pair<int, int> > q;
int d, s;
void lui(int i, int j) {
  if (M[i][j].first != -1) lui(M[i][j].first, M[i][j].second);
  cout << ok[i][j];
}
int main() {
  cin >> d >> s;
  for (int i = 1; i <= 9; ++i) {
    if (i == s && i % d == 0) {
      cout << i;
      return 0;
    }
    if (i <= s)
      q.push(pair<int, int>(i % d, i)), M[i % d][i] = pair<int, int>(-1, -1),
                                              vis[i % d][i] = 1,
                                              ok[i % d][i] = i;
  }
  pair<int, int> u, v;
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (int i = 0; i <= 9; ++i) {
      v = pair<int, int>((u.first * 10 + i) % d, u.second + i);
      if (v.second > s) continue;
      if (vis[v.first][v.second]) continue;
      q.push(v);
      M[v.first][v.second] = u;
      vis[v.first][v.second] = 1;
      ok[v.first][v.second] = i;
      if (v.first == 0 && v.second == s) {
        lui(v.first, v.second);
        return 0;
      }
    }
  }
  cout << -1;
  return 0;
}