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;
struct state {
  string s;
  int rem, sum;
};
int d, s, vis[501][5001];
queue<state> bfs;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> d >> s;
  for (int i = 1; i <= 9; i++) {
    string cur;
    cur += i + '0';
    bfs.push({cur, i % d, i});
  }
  while (bfs.size()) {
    auto cur = bfs.front();
    bfs.pop();
    if (cur.rem == 0 && cur.sum == s) return cout << cur.s << endl, 0;
    ;
    for (int j = 0; j <= 9; j++) {
      int rem = (cur.rem * 10 + j) % d;
      int sum = cur.sum + j;
      if (sum > s) continue;
      if (vis[rem][sum]) continue;
      vis[rem][sum] = 1;
      bfs.push({cur.s + char(j + '0'), rem, sum});
    }
  }
  cout << -1 << endl;
}