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 = 1000500;
const int M = 1000000;
int d, s;
int q[5005 * 505 * 2];
int dp[5005][505];
int pw[5005], qs, qt;
int p[5005][505];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> d >> s;
  pw[1] = 1;
  for (int i = 2; i <= 5000; ++i) pw[i] = pw[i - 1] * 10 % d;
  for (int i = 0; i <= s; ++i)
    for (int j = 0; j < d; ++j) dp[i][j] = 1e9;
  q[qt++] = 0, q[qt++] = 0;
  dp[0][0] = 0;
  while (qs < qt) {
    int i = q[qs++];
    int j = q[qs++];
    for (int dig = 0; dig < 10; ++dig) {
      if (dig + i <= s) {
        int nx = (j * 10 + dig) % d;
        int ns = dig + i;
        if (dp[ns][nx] > dp[i][j] + 1) {
          dp[ns][nx] = dp[i][j] + 1;
          q[qt++] = ns;
          q[qt++] = nx;
          p[ns][nx] = dig;
        }
      }
    }
  }
  if (dp[s][0] >= 1e9) return cout << -1, 0;
  int curs = s, curm = d % d;
  for (int i = dp[s][0]; i >= 1;) {
    for (int dig = (i == dp[s][0] ? 1 : 0); dig < 10; ++dig) {
      int ns = curs - dig;
      int nm = (curm - dig * pw[i] % d + d) % d;
      if (dp[ns][nm] < i) {
        cout << dig;
        int delta = i - dp[ns][nm] - 1;
        for (int k = 1; k <= delta; ++k) cout << 0;
        i = dp[ns][nm];
        curs = ns;
        curm = nm;
        break;
      }
    }
  }
  return 0;
}