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 INF = 1e9 + 7;
int d, s;
queue<pair<int, int> > q;
int dis[502][5002];
pair<int, pair<int, int> > pre[502][5002];
int main() {
  cin >> d >> s;
  for (int i = 0; i <= 500; i++)
    for (int j = 0; j <= 5000; j++) dis[i][j] = -1;
  for (int i = 1; i < 10; i++) {
    q.push(make_pair(i, i));
    dis[i][i] = 1;
    pre[i][i] = make_pair(i, make_pair(0, 0));
  }
  if (s % d == 0 && s <= 9) {
    printf("%d\n", s);
    return 0;
  }
  while (q.size()) {
    pair<int, int> p = q.front();
    q.pop();
    for (int i = 0; i < 10; i++) {
      int x = (10 * p.first + i) % d;
      int y = (p.second + i);
      if (y <= s && dis[x][y] == -1) {
        dis[x][y] = dis[p.first][p.second] + 1;
        q.push(make_pair(x, y));
        pre[x][y] = make_pair(i, p);
      }
    }
  }
  if (dis[0][s] == -1) {
    printf("-1\n");
    return 0;
  }
  vector<int> ans;
  pair<int, int> now = make_pair(0, s);
  while (true) {
    ans.push_back(pre[now.first][now.second].first);
    now = pre[now.first][now.second].second;
    if (now.second == 0) break;
  }
  for (int i = ans.size() - 1; i >= 0; i--) printf("%d", ans[i]);
}