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;
const int inf = 1e9 + 100500;
struct hmap {
  static int hash(unsigned x) {
    return ((x * 3) << 11) ^ (x >> 2) ^ ((x * 1000000007));
  }
  int sz;
  int cnt;
  int *ht, *val;
  hmap() : sz(4), cnt(0), ht(new int[sz]), val(new int[sz]) {
    memset(ht, -1, sz * sizeof(int));
    memset(val, 0, sz * sizeof(int));
  }
  ~hmap() {
    delete[] ht;
    delete[] val;
  }
  int getpos(int x) {
    if (cnt > sz / 2) {
      increase_capacity();
    }
    int i = abs(hash(x)) % sz;
    while (ht[i] != x && ht[i] != -1) {
      if (++i == sz) {
        i = 0;
      }
    }
    if (ht[i] == -1) {
      ht[i] = x;
      ++cnt;
    }
    return i;
  }
  int &operator[](int x) {
    int pos = getpos(x);
    return val[pos];
  }
  void increase_capacity() {
    int old_sz = sz;
    sz *= 4;
    int *ht1 = new int[sz];
    int *val1 = new int[sz];
    swap(ht, ht1);
    swap(val, val1);
    memset(ht, -1, sz * sizeof(int));
    memset(val, 0, sz * sizeof(int));
    cnt = 0;
    for (int i = 0; i < old_sz; ++i) {
      if (ht1[i] != -1) {
        (*this)[ht1[i]] = val1[i];
      }
    }
  }
};
template <typename T>
void last_digits(T &x, int &a, int &b) {
  T t = x / 10;
  a = x - t * 10;
  x = t;
  t = x / 10;
  b = x - t * 10;
  x = t;
}
template <typename T>
bool check(T x) {
  if (x < 100) return x % 11 != 0;
  int a, b;
  last_digits(x, a, b);
  if (a == b) return false;
  while (x) {
    int c = x % 10;
    x /= 10;
    if (c == b || (b < c) != (b < a)) return false;
    a = b;
    b = c;
  }
  return true;
}
bool check_k(int x, int k) {
  int a, b;
  last_digits(x, a, b);
  if (a == b) return false;
  for (int i = 0; i < (int)(k - 2); ++i) {
    int c = x % 10;
    x /= 10;
    if (c == b || (b < c) != (b < a)) return false;
    a = b;
    b = c;
  }
  return true;
}
long long n, k;
hmap d[10][2];
void fill() {
  for (int i = 0; i < (int)(10000000); ++i)
    if (check_k(i, 7)) {
      int a = i / 1000000;
      int b = (i % 1000000) / 100000;
      ++d[a][a < b][i % n];
    }
}
long long solve_small() {
  for (int i = 0; i < (int)(10000000); ++i) {
    if (i % n == 0 && check<int>(i)) {
      if (!--k) {
        return i;
      }
    }
  }
  return 0;
}
long long solve() {
  for (int st = (int)(1); st <= (int)(9999999); ++st)
    if (check<int>(st)) {
      long long rem = n - (((long long)st * 10000000) % n);
      if (rem == n) {
        rem = 0;
      }
      if (rem >= 10000000) {
        continue;
      }
      int a = (st % 100) / 10, b = st % 10;
      int local_s = 0;
      if (st < 10) {
        for (int t = 0; t < (int)(10); ++t)
          if (t != b) {
            local_s += d[t][t < b][rem];
          }
      } else if (a < b) {
        for (int t = 0; t < (int)(b); ++t) {
          local_s += d[t][t < b][rem];
        }
      } else if (a > b) {
        for (int t = b + 1; t < 10; ++t) {
          local_s += d[t][t < b][rem];
        }
      }
      if (local_s >= k) {
        for (int i = 0; i < (int)(10000000); ++i) {
          long long x = (long long)st * 10000000 + i;
          if (x % n == 0 && check<long long>(x)) {
            if (!--k) {
              return x;
            }
          }
        }
        assert(false);
      }
      k -= local_s;
    }
  return 0;
}
int main() {
  cin >> n >> k;
  long long res = solve_small();
  cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
  fill();
  if (res == 0) {
    cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
    res = solve();
  }
  assert(res % n == 0);
  assert(res == 0 || check(res));
  if (res == 0) {
    cout << -1 << endl;
  } else {
    cout << res << endl;
  }
  return 0;
}