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>
template <class T>
__inline__ __attribute__((always_inline)) bool chkmax(T &a, const T b) {
  return a < b ? ((a = b), 1) : 0;
}
template <class T>
__inline__ __attribute__((always_inline)) bool chkmin(T &a, const T b) {
  return a > b ? ((a = b), 1) : 0;
}
template <class T>
__inline__ __attribute__((always_inline)) T mymax(const T a, const T b) {
  return a > b ? a : b;
}
template <class T>
__inline__ __attribute__((always_inline)) T mymin(const T a, const T b) {
  return a < b ? a : b;
}
template <class T>
__inline__ __attribute__((always_inline)) T myabs(const T &a) {
  return a > 0 ? a : -a;
}
const int INF = 0X3F3F3F3F;
const double EPS = 1E-10, PI = acos(-1.0);
const int MAXN = 500 + 5, MAXM = 5000 + 5;
int d, s;
struct Graph {
  int dist[MAXN][MAXM], pre_edge[MAXN][MAXM], cnt;
  std::pair<int, int> pre_node[MAXN][MAXM];
  bool vis[MAXN][MAXM];
  void BFS() {
    static std::pair<int, int> que[MAXN * MAXM];
    memset(dist, 63, sizeof dist);
    int l = 1, r = 0;
    que[++r] = std::make_pair(0, s);
    vis[0][s] = 1;
    while (l <= r) {
      std::pair<int, int> u = que[l++];
      for (int i = 0, iend = 9; i <= iend; ++i) {
        std::pair<int, int> temp =
            std::make_pair((u.first * 10 + i) % d, u.second - i);
        if (u.second >= i && !vis[temp.first][temp.second]) {
          vis[temp.first][temp.second] = 1;
          pre_node[temp.first][temp.second] = u;
          pre_edge[temp.first][temp.second] = i;
          dist[temp.first][temp.second] = dist[u.first][u.second] + 1;
          que[++r] = temp;
        }
      }
    }
  }
  void print() {
    if (!vis[0][0]) {
      puts("-1");
      return;
    }
    static int stack[MAXM];
    int top = 0;
    std::pair<int, int> cur = std::make_pair(0, 0), end = std::make_pair(0, s);
    while (cur != end) {
      stack[++top] = pre_edge[cur.first][cur.second];
      cur = pre_node[cur.first][cur.second];
    }
    for (int i = top, iend = 1; i >= iend; --i) printf("%d", stack[i]);
    puts("");
  }
} G;
int main() {
  scanf("%d%d", &d, &s);
  G.BFS();
  G.print();
  return 0;
}