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 data {
  int start;
  int awal;
  int panjang;
  int last;
  int val;
};
vector<int> v[10];
unordered_map<int, int> asu[10][2][10];
long long n, k;
inline bool isWavy(long long x) {
  bool naikTurun = 1;
  bool turunNaik = 1;
  int last = x % 10;
  int iter = 0;
  x /= 10;
  while (x > 0 && (naikTurun || turunNaik)) {
    int cur = x % 10;
    iter++;
    x /= 10;
    if (iter & 1) {
      naikTurun &= (cur > last);
      turunNaik &= (cur < last);
    } else {
      naikTurun &= (cur < last);
      turunNaik &= (cur > last);
    }
    last = cur;
  }
  return naikTurun || turunNaik;
}
inline bool getStat(int x) {
  int lst = x % 10;
  int lst2 = x % 100;
  lst2 /= 10;
  return (lst2 < lst);
}
inline int getLen(int x) {
  if (x == 0) return 1;
  int ret = 0;
  while (x) {
    ret++;
    x /= 10;
  }
  return ret;
}
inline int getCount(int panjang, int awal, int start, long long x) {
  if (x > (long long)1e7) return 0;
  return asu[panjang][awal][start].count(x) ? asu[panjang][awal][start][x] : 0;
}
void prec() {
  queue<data> q;
  for (int i = 0; i < 10; i++) {
    if (i < 9) q.push((data){i, 1, 1, i, i});
    if (i > 0) q.push((data){i, 0, 1, i, i});
  }
  while (!q.empty()) {
    data now = q.front();
    q.pop();
    asu[now.panjang][now.awal][now.start][now.val % n]++;
    v[now.panjang].push_back(now.val);
    if (now.panjang + 1 < 8) {
      int stat = (now.awal + now.panjang + 1) & 1;
      if (stat) {
        for (int i = now.last + 1; i < 10; i++)
          q.push((data){now.start, now.awal, now.panjang + 1, i,
                        now.val * 10 + i});
      } else {
        for (int i = 0; i < now.last; i++)
          q.push((data){now.start, now.awal, now.panjang + 1, i,
                        now.val * 10 + i});
      }
    }
  }
  for (int i = 1; i < 8; i++) sort(v[i].begin(), v[i].end());
}
void solve() {
  for (int i = 1; i < 1000; i++)
    if (i % n == 0 && isWavy(i)) {
      k--;
      if (k == 0) {
        printf("%d\n", i);
        exit(0);
      }
    }
  int lstart = -1;
  int xstart = -1;
  int astart = -1;
  for (int len = 4; len <= 14; len++) {
    int mid = len / 2;
    int sisa = len - mid;
    long long mul = 1;
    for (int i = 0; i < sisa; i++) mul = (mul * 10) % n;
    for (int x : v[mid]) {
      int lenx = getLen(x);
      if (lenx < mid) continue;
      bool stat = getStat(x);
      int lst = x % 10;
      long long cur = (mul * x) % n;
      long long need = (n - cur) % n;
      if (stat) {
        for (int i = 0; i < lst; i++) {
          int lol = getCount(sisa, stat, i, need);
          if (lol >= k) {
            lstart = len;
            xstart = x;
            astart = i;
            goto shitjustgotreal;
          }
          k -= lol;
        }
      } else {
        for (int i = lst + 1; i < 10; i++) {
          int lol = getCount(sisa, stat, i, need);
          if (lol >= k) {
            lstart = len;
            xstart = x;
            astart = i;
            goto shitjustgotreal;
          }
          k -= lol;
        }
      }
    }
  }
  puts("-1");
  return;
shitjustgotreal:
  int stat = getStat(xstart);
  int mid = lstart / 2;
  int sisa = lstart - mid;
  long long mul = 1;
  for (int i = 0; i < sisa; i++) mul = (mul * 10) % n;
  long long cur = (mul * xstart) % n;
  long long need = (n - cur) % n;
  for (int x : v[sisa]) {
    int haha = x;
    for (int i = 0; i < sisa - 2; i++) haha /= 10;
    int kedua = haha % 10;
    int pertama = haha / 10;
    if (pertama == astart &&
        ((stat == 1 && pertama < kedua) || (stat == 0 && pertama > kedua)) &&
        x % n == need) {
      k--;
      if (k == 0) {
        printf("%d", xstart);
        if (pertama == 0) printf("0");
        printf("%d\n", x);
        break;
      }
    }
  }
  assert(k == 0);
}
int main() {
  cin >> n >> k;
  prec();
  solve();
  return 0;
}