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 = 505, M = 5005;
int d, s, vis[N][M], num[N][M];
pair<int, int> last[N][M];
queue<pair<int, int> > Q;
int main() {
  scanf("%d%d", &d, &s);
  vis[0][0] = 1;
  Q.push(make_pair(0, 0));
  while (!Q.empty()) {
    pair<int, int> now = Q.front();
    Q.pop();
    for (int i = 0; i <= 9; i++) {
      pair<int, int> nxt = make_pair((now.first * 10 + i) % d, now.second + i);
      if (vis[nxt.first][nxt.second] || nxt.second > s) continue;
      Q.push(nxt);
      vis[nxt.first][nxt.second] = vis[now.first][now.second] + 1;
      num[nxt.first][nxt.second] = i;
      last[nxt.first][nxt.second] = now;
    }
  }
  if (vis[0][s] == 0) {
    puts("-1");
    return 0;
  }
  string ans;
  for (auto now = make_pair(0, s);; now = last[now.first][now.second]) {
    if (now.first == 0 && now.second == 0) break;
    ans += (num[now.first][now.second] + '0');
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0;
}