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;
template <class T>
T read() {
  T t;
  cin >> t;
  return t;
}
const int cache_sz = 1000;
bool cache[cache_sz];
bool is_wavy(long long x, bool& up) {
  if (!cache[x % cache_sz]) return false;
  int last2 = x % 100;
  int d2 = last2 % 10;
  int d1 = last2 / 10;
  if (d1 == d2) return false;
  up = d1 > d2;
  if (x < 100) return true;
  x /= 100;
  for (; x; x /= 10, up = !up) {
    d2 = x % 10;
    swap(d2, d1);
    if (d2 == d1 || up && d1 > d2 || !up && d1 < d2) return false;
  }
  return true;
}
bool is_wavy(long long x) {
  bool up;
  return is_wavy(x, up);
}
long long ipow(long long a, long long p) {
  return (!p) ? 1 : a * ipow(a, p - 1);
}
void solve() {
  const long long n = read<long long>();
  const long long k = read<long long>();
  const int half_order = 7;
  const long long half = ipow(10, half_order);
  fill(cache, cache + cache_sz, true);
  for (int i = (1); i < (int)(cache_sz); i++) cache[i] = is_wavy(i);
  long long lk = k;
  long long ans;
  vector<int> small_wavy;
  small_wavy.reserve(half);
  unordered_map<long long, array<vector<int>, 10> > wavy_by_reminder_and_up[2];
  for (int i = (0); i < (int)(half); i++) {
    bool up;
    if (is_wavy(i, up)) {
      if (i % n == 0) {
        --lk;
        if (!lk) {
          ans = i;
        }
      }
      if (i) small_wavy.push_back(i);
      int first_digit = i / (half / 10);
      if (first_digit == 0) {
        if (!up || i < half / 100) continue;
        up = false;
      }
      wavy_by_reminder_and_up[int(up)][i % n][first_digit].push_back(i);
    }
  }
  if (lk <= 0) {
    cout << ans << endl;
    return;
  }
  const long long half_remainder = half % n;
  const long long antihalf_remainder = (n - half_remainder) % n;
  for (long long i : small_wavy) {
    if (i >= 10) break;
    long long rem = i * antihalf_remainder % n;
    if (rem >= half) continue;
    int big_d1 = (i / 10) % 10;
    int big_d2 = i % 10;
    bool last_up = big_d1 > big_d2;
    for (int big_d3 = (0); big_d3 < (int)(10); big_d3++) {
      if (i < 10) {
        last_up = big_d2 < big_d3;
      }
      if (big_d3 == big_d2 || last_up && big_d2 > big_d3 ||
          !last_up && big_d2 < big_d3) {
        continue;
      }
      auto& hash = wavy_by_reminder_and_up[last_up];
      auto it = hash.find(rem);
      if (it != hash.end()) {
        auto& tails = it->second[big_d3];
        if (tails.size() >= lk) {
          cout << i * half + tails[lk - 1] << endl;
          return;
        }
        lk -= tails.size();
      }
    }
  }
  for (long long i : small_wavy) {
    if (i < 10) continue;
    long long rem = ((-i * half_remainder % n) + n) % n;
    if (rem >= half) continue;
    int big_d1 = (i / 10) % 10;
    int big_d2 = i % 10;
    bool last_up = big_d1 > big_d2;
    auto& hash = wavy_by_reminder_and_up[last_up];
    auto it = hash.find(rem);
    if (it == hash.end()) {
      continue;
    }
    for (int big_d3 = (0); big_d3 < (int)(10); big_d3++) {
      if (big_d3 == big_d2 || last_up && big_d2 > big_d3 ||
          !last_up && big_d2 < big_d3) {
        continue;
      }
      auto& tails = it->second[big_d3];
      if (tails.size() >= lk) {
        cout << i * half + tails[lk - 1] << endl;
        return;
      }
      lk -= tails.size();
    }
  }
  cout << -1;
}
int main() {
  solve();
  return 0;
}