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;
#pragma GCC optimize(2)
struct MyStruct {
  int x;
  int s;
  string abc;
};
queue<MyStruct> q;
int d, s;
int vis[600][6000];
int main() {
  cin >> d >> s;
  for (int i = 1; i <= 9; i++) {
    MyStruct newNode;
    newNode.x = i % d;
    newNode.s = i;
    newNode.abc += char(i + '0');
    q.push(newNode);
    if (i == s && i % d == 0) {
      cout << i;
      return 0;
    }
  }
  while (!q.empty()) {
    MyStruct newNode = q.front();
    q.pop();
    for (int i = 0; i <= 9; i++) {
      if (vis[(newNode.x * 10 + i) % d][newNode.s + i]) continue;
      if (newNode.s + i > s) {
        continue;
      }
      MyStruct NowNode;
      NowNode.x = (newNode.x * 10 + i) % d;
      NowNode.s = newNode.s + i;
      NowNode.abc = newNode.abc + char(i + '0');
      vis[(newNode.x * 10 + i) % d][newNode.s + i] = 1;
      q.push(NowNode);
      if (NowNode.x == 0 && NowNode.s == s) {
        cout << NowNode.abc;
        return 0;
      }
    }
  }
  cout << -1;
  return 0;
}