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>
#pragma GCC optimize("3,Ofast,inline")
using namespace std;
int d, s, len[510][5010];
bool vis[510][5010];
int dp[510][5010];
pair<int, int> nxt[510][5010], ans;
int dfs(int ys, int sum) {
  if (!sum && !ys) return 0;
  if (vis[ys][sum]) return dp[ys][sum];
  vis[ys][sum] = 1;
  dp[ys][sum] = 0x3f3f3f3f;
  int i, tmp;
  for (i = min(sum, 9); i >= 0; i--) {
    tmp = dfs((ys * 10 + i) % d, sum - i);
    if (tmp >= 0x3f3f3f3f) continue;
    if (dp[ys][sum] == 0x3f3f3f3f) {
      dp[ys][sum] = tmp + 1;
      nxt[ys][sum] = make_pair((ys * 10 + i) % d, sum - i);
      continue;
    }
    if (tmp + 1 <= dp[ys][sum]) {
      dp[ys][sum] = tmp + 1;
      nxt[ys][sum] = make_pair((ys * 10 + i) % d, sum - i);
    }
  }
  return dp[ys][sum];
}
inline void out(int u, int v) {
  if (!v && !u) return;
  printf("%d", v - nxt[u][v].second);
  out(nxt[u][v].first, nxt[u][v].second);
}
int main() {
  int i, j, tmp, l = 0x3f3f3f3f, t;
  cin >> d >> s;
  for (i = min(s, 9); i >= 1; i--) {
    tmp = dfs(i % d, s - i);
    if (tmp <= l) {
      t = i;
      l = tmp;
      ans = make_pair(i % d, s - i);
    }
  }
  if (l == 0x3f3f3f3f)
    puts("-1");
  else {
    cout << t;
    out(ans.first, ans.second);
  }
}