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;
template <typename Tx, typename Ty>
struct Point2D {
  Point2D() {}
  Point2D(const Point2D<Tx, Ty> &V) {
    x = V.x;
    y = V.y;
  }
  Tx x;
  Ty y;
};
template <typename Tx, typename Ty>
inline Point2D<Tx, Ty> Trans(const Tx &tx, const Ty &ty) {
  static Point2D<Tx, Ty> P;
  P.x = tx;
  P.y = ty;
  return P;
}
template <const int Size, typename Type>
class Queue {
 public:
  Queue() { Head = Tail = 0; }
  inline Type Pushin(const Type &Value) { return q[Head++] = Value; }
  inline Type Popsit() { return q[Tail++]; }
  inline Type Fronts() { return q[Tail]; }
  inline unsigned int Sizeof() { return Head - Tail; }
  inline bool Empty() { return Head == Tail; }
  inline bool Nmpty() { return Head != Tail; }

 private:
  Type q[Size];
  unsigned int Head, Tail;
};
int d, s;
bool vis[567][5678];
int pre[567][5678][3];
Queue<5678 * 567 + 2, Point2D<int, int> > Qx, Qy;
inline void bfs() {
  vis[0][0] = 1;
  Qx.Pushin(Trans(0, 0));
  while (Qx.Nmpty()) {
    Point2D<int, int> t = Qx.Popsit();
    for (int i = 0; i <= 9; ++i) {
      int tx = ((t.x << 3) + (t.x << 1) + i) % d, ty = t.y + i;
      if (vis[tx][ty] || ty > s) continue;
      vis[tx][ty] = 1;
      pre[tx][ty][0] = t.x;
      pre[tx][ty][1] = t.y;
      pre[tx][ty][2] = i;
      Qx.Pushin(Trans(tx, ty));
    }
  }
}
void Printf(const int y, const int x = 0) {
  if (x || y) Printf(pre[x][y][1], pre[x][y][0]), printf("%d", pre[x][y][2]);
}
int main() {
  cin >> d >> s;
  bfs();
  if (vis[0][s] == 0)
    puts("-1");
  else
    Printf(s);
  return 0;
}