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;
struct Rec {
  int r;
  int i, j;
  int cnt;
  Rec() {}
  Rec(int r, int i, int j) : r(r), i(i), j(j) {}
};
inline bool operator<(const Rec& a, const Rec& b) {
  if (a.r != b.r) return a.r < b.r;
  if (a.i != b.i) return a.i < b.i;
  return a.j < b.j;
}
inline bool operator==(const Rec& a, const Rec& b) {
  if (a.r != b.r) return false;
  if (a.i != b.i) return false;
  return a.j == b.j;
}
int digits[10];
int nd;
vector<Rec> vr;
bool good[10][10][10][10];
bool good3[10][10][10];
bool ok() {
  int i = 1;
  while (i + 1 < nd) {
    if (!(digits[i] > digits[i - 1] && digits[i] > digits[i + 1]) &&
        !(digits[i] < digits[i - 1] && digits[i] < digits[i + 1])) {
      return false;
    }
    i++;
  }
  return true;
}
bool isWave(int n) {
  nd = 0;
  int i = 1;
  while (n) {
    if (nd && digits[nd - 1] == n % 10) return false;
    digits[nd++] = n % 10;
    n /= 10;
    while (i + 1 < nd) {
      if (!(digits[i] > digits[i - 1] && digits[i] > digits[i + 1]) &&
          !(digits[i] < digits[i - 1] && digits[i] < digits[i + 1])) {
        return false;
      }
      i++;
    }
  }
  return true;
}
long long n, k;
string num(int l, int r) {
  ostringstream out;
  out << l;
  if (r < 1000000) out << 0;
  out << r;
  string digits = out.str();
  for (int i = 1; i + 1 < digits.size(); i++) {
    if (!(digits[i] > digits[i - 1] && digits[i] > digits[i + 1]) &&
        !(digits[i] < digits[i - 1] && digits[i] < digits[i + 1])) {
      cerr << "not wave: " << digits << endl;
      exit(1);
    }
  }
  istringstream in(digits);
  long long x;
  in >> x;
  if (x % n) {
    cerr << "not 0 remainder: " << digits << endl;
  }
  return digits;
}
int main() {
  cin >> n >> k;
  vector<int> wave, waveR;
  for (int i = 1; i < 10000000; i++) {
    if (isWave(i)) {
      if (i % n == 0) {
        k--;
        if (k == 0) {
          cout << i << endl;
          return 0;
        }
      }
      if (i >= 100000) {
        if (nd < 7) {
          digits[nd++] = 0;
        }
        if (ok()) {
          vr.push_back(Rec(i % n, digits[6], digits[5]));
          waveR.push_back(i);
        }
      }
      wave.push_back(i);
    }
  }
  sort(vr.begin(), vr.end());
  vector<Rec> tr = vr;
  vr.clear();
  int l = 0;
  while (l < tr.size()) {
    int r = l;
    while (r < tr.size() && tr[l] == tr[r]) r++;
    Rec rec = tr[l];
    rec.cnt = r - l;
    vr.push_back(rec);
    l = r;
  }
  for (int i0 = 0; i0 < (int)(10); i0++) {
    for (int i1 = 0; i1 < (int)(10); i1++) {
      for (int i2 = 0; i2 < (int)(10); i2++) {
        for (int i3 = 0; i3 < (int)(10); i3++) {
          digits[0] = i0;
          digits[1] = i1;
          digits[2] = i2;
          nd = 3;
          good3[i0][i1][i2] = ok();
          digits[3] = i3;
          nd = 4;
          good[i0][i1][i2][i3] = ok();
        }
      }
    }
  }
  cerr << wave.size() << endl;
  for (int w : wave) {
    long long need = ((-w * 10000000ll % n) + n) % n;
    if (need >= 1e7) continue;
    int d0 = w % 10;
    int d1 = (w / 10) % 10;
    auto p = lower_bound(vr.begin(), vr.end(), Rec((int)need, -1, -1));
    while (p != vr.end() && p->r == need) {
      int i = p->i;
      int j = p->j;
      if (w > 9 && !good[d1][d0][i][j]) {
        p++;
        continue;
      }
      if (w < 10 && !good3[d0][i][j]) {
        p++;
        continue;
      }
      if (k <= p->cnt) {
        for (int r : waveR) {
          if (r % n != need) continue;
          int ci = r / 1000000;
          int cj = (r % 1000000) / 100000;
          if (ci == i && cj == j) {
            k--;
            if (k == 0) {
              cout << num(w, r) << endl;
              return 0;
            }
          }
        }
      } else {
        k -= p->cnt;
      }
      p++;
    }
  }
  cout << -1 << endl;
  return 0;
}