Problem: A wavy number is such positive integer that for any digit of its decimal representation except for the first one and the last one following condition holds: the digit is either strictly larger than both its adjacent digits or strictly less than both its adjacent digits. For example, numbers 35270, 102, 747, 20 and 3 are wavy and numbers 123, 1000 and 2212 are not.

The task is to find the k-th smallest wavy number r that is divisible by n for the given integer values n and k.

You are to write a program that will find the value of r if it doesn't exceed 1014.

Input

The only line of input contains two integers n and k, separated by a single space (1 ≤ n, k ≤ 1014). 

Output

Your task is to output the only integer r — the answer to the given problem. If such number does not exist or it is larger than 1014, then print "-1" (minus one without the quotes) instead.

Examples

Input

123 4


Output

1845


Input

100 1


Output

-1


Input

97461 457


Output

1805270103

Note

The values of the first four wavy numbers that are divisible by n for the first sample are: 492, 615, 738 and 1845.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long n, k;
vector<long long> wave, twave;
long ttl[10][2][1000000];
long long ans;
long long nice, ld;
long long need, req;
long long pref, temp;
void generate(long ps, bool up, long ldig, long val) {
  if (val > 0) wave.push_back(val);
  if (ps == 7) {
    ttl[val / 1000000][up][(val % 1000000) % n]++;
    return;
  }
  for (int ad = 0; ad < 10; ad++) {
    if (ad > ldig && up == 1) generate(ps + 1, !up, ad, val * 10 + ad);
    if (ad < ldig && up == 0) generate(ps + 1, !up, ad, val * 10 + ad);
  }
}
void check(long long x) {
  if (k <= 0) return;
  --k;
  if (k == 0) ans = x;
}
long get_dir(long x) {
  if (x < 10) return 3;
  int d1, d2;
  d2 = x % 10;
  d1 = x % 100 / 10;
  if (d1 < d2) return 2;
  return 1;
}
bool iswave(long long x) {
  if (x < 10) return 1;
  vector<long> v;
  while (x) {
    v.push_back(x % 10);
    x = x / 10;
  }
  if (v[0] == v[1]) return 0;
  bool o = (v[0] < v[1]);
  for (int i = 1; i + 1 < v.size(); i++) {
    if (o == 0 && v[i + 1] <= v[i]) return 0;
    if (o == 1 && v[i + 1] >= v[i]) return 0;
    o = 1 - o;
  }
  return 1;
}
int main() {
  cin >> n >> k;
  generate(0, 1, -100, 0);
  generate(0, 0, 100, 0);
  sort(wave.begin(), wave.end());
  twave = wave;
  wave.clear();
  for (int i = 0; i < twave.size(); i++)
    if (i == 0 || twave[i] != twave[i - 1]) wave.push_back(twave[i]);
  ans = -1;
  for (int i = 0; i < wave.size(); i++) {
    if (wave[i] % n == 0 && k > 0) check(wave[i]);
  }
  for (int i = 0; i < wave.size(); i++) {
    if (ans != -1) continue;
    nice = 0;
    int dirm = get_dir(wave[i]);
    ld = wave[i] % 10;
    need = 1ll * wave[i] * 10000000 % n;
    need = n - need;
    if (need == n) need = 0;
    if (need > 10000000) continue;
    for (int dir = 1; dir <= 2; dir++)
      if (dirm & dir)
        for (int fdig = 0; fdig < 10; fdig++) {
          if (dir == 1 && fdig <= ld) continue;
          if (dir == 2 && fdig >= ld) continue;
          req = need - fdig * 1000000 % n;
          req = req % n;
          while (req < 0) req += n;
          if (req < 1000000) nice += ttl[fdig][dir - 1][req];
        }
    if (nice < k) {
      k -= nice;
      continue;
    }
    pref = wave[i] * 10000000;
    for (int j = 0; j < wave.size(); j++) {
      temp = pref + wave[j];
      if (iswave(temp) == 1 && temp % n == 0) check(temp);
    }
  }
  cout << ans;
  return 0;
}