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 = 500 + 10;
int p, s;
int vis[maxn][maxn * 10];
struct ZT {
  int r, sum;
};
ZT pre[maxn][maxn * 10];
queue<ZT> qu;
int cur, a[maxn * maxn];
int main() {
  while (~scanf("%d%d", &p, &s)) {
    memset(vis, 0, sizeof(vis));
    while (!qu.empty()) qu.pop();
    for (int k = (1); k <= (9); ++k)
      if (k <= s) {
        ZT no0;
        no0.r = k % p;
        no0.sum = k;
        vis[no0.r][no0.sum] = 1;
        pre[no0.r][no0.sum] = (ZT){-1, 0};
        qu.push(no0);
      }
    while (!qu.empty()) {
      ZT no = qu.front();
      qu.pop();
      if (no.r == 0 && no.sum == s) {
        cur = 0;
        while (no.r != -1) {
          a[++cur] = no.sum - pre[no.r][no.sum].sum;
          no = pre[no.r][no.sum];
        }
        for (int i = (cur); i >= (1); --i) cout << a[i];
        cout << endl;
        goto End;
      }
      for (int k = (0); k <= (9); ++k)
        if (no.sum + k <= s) {
          ZT nx;
          nx.r = (no.r * 10 + k) % p;
          nx.sum = no.sum + k;
          if (vis[nx.r][nx.sum]) continue;
          vis[nx.r][nx.sum] = 1;
          pre[nx.r][nx.sum] = no;
          qu.push(nx);
        }
    }
    cout << -1 << endl;
  End:
    continue;
  }
  return 0;
}