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 node {
  bool visited;
  short prex;
  short prey;
  short val;
  node() { visited = false; }
  void print() {
    cout << visited << " (" << prex << ", " << prey << ") " << val << endl;
  }
};
struct coord {
  int x, y;
  coord(int x, int y) {
    this->x = x;
    this->y = y;
  }
};
class SpecialNum {
 public:
  SpecialNum(int d, int s) {
    this->d = d;
    this->s = s;
    init();
  }
  bool get() { return get(0, s); }
  bool get(int x, int y);

 private:
  int d, s;
  node** table = 0;
  void init() {
    table = new node*[d];
    for (int i = 0; i < d; i++) table[i] = new node[s + 1];
    bfs();
  }
  void bfs();
};
void SpecialNum::bfs() {
  queue<coord> que;
  int nextx = 0, nexty = 0;
  que.push(coord(0, 0));
  while (!que.empty()) {
    coord cur = que.front();
    que.pop();
    for (int i = 0; i < 10; i++) {
      nextx = (10 * cur.x + i) % d;
      nexty = cur.y + i;
      if (table[nextx][nexty].visited || nexty > s) continue;
      table[nextx][nexty].visited = true;
      table[nextx][nexty].prex = cur.x;
      table[nextx][nexty].prey = cur.y;
      table[nextx][nexty].val = i;
      que.push(coord(nextx, nexty));
    }
  }
}
bool SpecialNum::get(int x, int y) {
  if (!table[x][y].visited || (x == 0 && y == 0)) return false;
  get(table[x][y].prex, table[x][y].prey);
  cout << table[x][y].val;
  return true;
}
int main() {
  int d, s;
  cin >> d >> s;
  SpecialNum* sn = new SpecialNum(d, s);
  if (!sn->get()) cout << -1;
  cout << endl;
}