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 maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int d, s, cnt;
char ans[maxn];
int dis[510][5010];
int inq[510][5010];
int vis[510][5010];
struct node {
  int remind;
  int sum;
  node() {}
  node(int remind, int sum) : remind(remind), sum(sum) {}
};
void Init() {
  cnt = -1;
  memset(inq, 0, sizeof inq);
  memset(dis, 0x3f, sizeof dis);
  memset(vis, 0, sizeof vis);
}
void BFS() {
  queue<node> q;
  dis[0][0] = 0;
  q.push(node(0, 0));
  inq[0][0] = 1;
  while (!q.empty()) {
    node st = q.front();
    q.pop();
    inq[st.remind][st.sum] = 0;
    for (int i = 0; i < 10; ++i) {
      node now = node((st.remind * 10 + i) % d, st.sum + i);
      if (now.sum > s) break;
      if (dis[now.remind][now.sum] > dis[st.remind][st.sum] + 1) {
        dis[now.remind][now.sum] = dis[st.remind][st.sum] + 1;
        if (!inq[now.remind][now.sum]) {
          inq[now.remind][now.sum] = 1;
          q.push(now);
        }
      }
    }
  }
}
int DFS(int D, int S) {
  if (D == 0 && S == s) return 1;
  for (int i = 0; i < 10; ++i) {
    int td = (D * 10 + i) % d;
    int ts = S + i;
    if (ts > s) break;
    if (vis[td][ts]) continue;
    if (dis[D][S] + 1 != dis[td][ts]) continue;
    ans[++cnt] = i;
    if (DFS(td, ts)) return 1;
    --cnt;
  }
  vis[D][S] = 1;
  return 0;
}
int main() {
  while (~scanf("%d %d", &d, &s)) {
    Init();
    BFS();
    if (dis[0][s] == INF) {
      puts("-1");
      continue;
    }
    DFS(0, 0);
    for (int i = 0; i <= cnt; ++i) printf("%d", ans[i]);
    puts("");
  }
  return 0;
}