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;
bool Free[5005][505][2];
int d, s;
vector<int> V;
queue<pair<pair<int, int>, int> > Q;
pair<pair<int, int>, pair<int, int> > Trace[5005][505][2];
void Path(int A, int B, int C) {
  while (A > 0 || B > 0 || C > 0) {
    V.push_back(Trace[A][B][C].second.second);
    int nA = Trace[A][B][C].first.first;
    int nB = Trace[A][B][C].first.second;
    int nC = Trace[A][B][C].second.first;
    A = nA;
    B = nB;
    C = nC;
  }
  reverse(V.begin(), V.end());
  for (auto x : V) cout << x;
}
int main() {
  cin >> d >> s;
  Q.push(pair<pair<int, int>, int>(pair<int, int>(0, 0), 0));
  Free[0][0][0] = true;
  while (Q.size() > 0) {
    int sum = Q.front().first.first;
    int rem = Q.front().first.second;
    int lead = Q.front().second;
    Q.pop();
    if (sum == s && rem == 0) {
      Path(sum, rem, lead);
      return 0;
    }
    for (int i = 1 - lead; i <= 9; i++)
      if (sum + i <= s) {
        int newsum = sum + i;
        int newrem = (rem * 10 + i) % d;
        int newlead = lead | (i > 0);
        if (Free[newsum][newrem][newlead] == false) {
          Free[newsum][newrem][newlead] = true;
          Trace[newsum][newrem][newlead] =
              pair<pair<int, int>, pair<int, int> >(pair<int, int>(sum, rem),
                                                    pair<int, int>(lead, i));
          Q.push(pair<pair<int, int>, int>(pair<int, int>(newsum, newrem),
                                           newlead));
        }
      }
  }
  cout << -1;
}