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;
int d, s;
int E[2510050][10];
int Get(int x, int y) { return x * d + y; }
int dis[2710500];
char ok[2700050] = {};
vector<int> ans;
int ST, EN;
int dfs(int x) {
  if (x == EN) return 1;
  ok[x] = 1;
  for (int u = 0; u < 10; u++)
    if (x != 0 || u != 0) {
      int v = E[x][u];
      if (dis[v] == dis[x] + 1 && ok[v] == 0) {
        ans.push_back(u);
        if (dfs(v)) return 1;
        ans.pop_back();
      }
    }
  return 0;
}
int main() {
  scanf("%d%d", &d, &s);
  for (int i = 0; i <= s; i++)
    for (int j = 0; j < d; j++) {
      int x = Get(i, j);
      for (int e = 0; e < 10; e++) {
        if (i == 0 && j == 0 && e == 0) continue;
        int ni = i + e;
        int nj = (10 * j + e) % d;
        if (ni <= s) {
          int xx = Get(ni, nj);
          E[x][e] = xx;
        }
      }
    }
  ST = Get(0, 0), EN = Get(s, 0);
  vector<int> v;
  v.push_back(ST);
  memset(dis, -1, sizeof dis);
  dis[ST] = 0;
  for (int i = 0; i < (int)v.size(); i++) {
    int t = v[i];
    for (int u = 0; u < 10; u++)
      if (t != 0 || u != 0) {
        int w = E[t][u];
        if (dis[w] == -1) {
          dis[w] = dis[t] + 1;
          v.push_back(w);
        }
      }
  }
  if (dis[EN] == -1)
    puts("-1");
  else {
    dfs(ST);
    for (int e : ans) printf("%d", e);
    puts("");
  }
}