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 N = 2e5 + 2;
const int D = 5e2 + 2;
const int S = 5e3 + 2;
int d, s, vis[D][S], pre[D][S][3];
queue<pair<int, int>> q;
template <typename _Tp>
inline void IN(_Tp& x) {
  char ch;
  bool flag = 0;
  x = 0;
  while (ch = getchar(), !isdigit(ch))
    if (ch == '-') flag = 1;
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  if (flag) x = -x;
}
inline void bfs() {
  q.push(make_pair(0, 0)), vis[0][0] = 1;
  while (!q.empty()) {
    int x = q.front().first, y = q.front().second;
    q.pop();
    for (int num = 0; num <= 9; ++num) {
      int xx = (x * 10 + num) % d, yy = y + num;
      if (vis[xx][yy] || yy > s) continue;
      pre[xx][yy][0] = x, pre[xx][yy][1] = y, pre[xx][yy][2] = num;
      vis[xx][yy] = 1;
      q.push(make_pair(xx, yy));
    }
  }
}
void output(int x, int y) {
  if (!x && !y) return;
  output(pre[x][y][0], pre[x][y][1]);
  printf("%d", pre[x][y][2]);
}
int main() {
  IN(d), IN(s);
  bfs();
  if (!vis[0][s])
    puts("-1");
  else
    output(0, s), puts("");
  return 0;
}