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<int> l;
vector<pair<int, int> > r[10][2];
inline bool check(long long x) {
  if (x < 100) return true;
  int now = x % 10;
  x /= 10;
  if (x % 10 == now) return false;
  bool b;
  if (x % 10 > now)
    b = true;
  else
    b = false;
  now = x % 10;
  x /= 10;
  while (x) {
    b = !b;
    if (b && x % 10 <= now) return false;
    if (!b && x % 10 >= now) return false;
    now = x % 10;
    x /= 10;
  }
  return true;
}
void dfsl(int d, int x, int last1, int last2) {
  if (d > 7) return;
  l.push_back(x);
  for (int i = 0; i < 10; i++) {
    if (i == last2) continue;
    if (last1 < last2 && last2 < i) continue;
    if (last1 > last2 && last2 > i) continue;
    dfsl(d + 1, x * 10 + i, last2, i);
  }
}
void dfsr(int d, int x, int start1, int start2, int last1, int last2) {
  if (d == 7) {
    if (start1 < start2) {
      for (int i = start1; i < 10; i++)
        r[i][start1 < start2].push_back(make_pair(x % n, x));
    } else {
      for (int i = start1; i >= 0; i--)
        r[i][start1 < start2].push_back(make_pair(x % n, x));
    }
    return;
  }
  for (int i = 0; i < 10; i++) {
    if (i == last2) continue;
    if (last1 < last2 && last2 < i) continue;
    if (last1 > last2 && last2 > i) continue;
    dfsr(d + 1, x * 10 + i, start1, start2, last2, i);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k;
  if (n >= 1e8) {
    for (long long i = n; i <= 1e14; i += n) {
      if (check(i)) {
        k--;
        if (k == 0) {
          cout << i << endl;
          return 0;
        }
      }
    }
    cout << -1 << endl;
    return 0;
  }
  for (int i = 1; i < 10; i++) {
    l.push_back(i);
  }
  for (int i = 1; i < 10; i++)
    for (int j = 0; j < 10; j++)
      if (i != j) dfsl(2, i * 10 + j, i, j);
  for (int i = 0; i < 10; i++)
    for (int j = 0; j < 10; j++)
      if (i != j) dfsr(2, i * 10 + j, i, j, i, j);
  sort(l.begin(), l.end());
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 2; j++) {
      sort(r[i][j].begin(), r[i][j].end());
    }
  }
  for (int i = 0; i < l.size(); i++) {
    if (l[i] % n == 0) {
      k--;
      if (k == 0) {
        cout << l[i] << endl;
        return 0;
      }
    }
  }
  for (int i = 0; i < l.size(); i++) {
    int x = l[i];
    int vl = l[i];
    int needmod = (n - vl % n * 10000000LL % n) % n;
    if (x % 10 > 0 && (x < 10 || x / 10 % 10 < x % 10)) {
      vector<pair<int, int> >& vecr = r[x % 10 - 1][1];
      int pl = lower_bound(vecr.begin(), vecr.end(), make_pair(needmod, 0)) -
               vecr.begin();
      int pr =
          lower_bound(vecr.begin(), vecr.end(), make_pair(needmod + 1, 0)) -
          vecr.begin();
      if (pr - pl < k) {
        k -= pr - pl;
      } else {
        cout << (vl * 10000000LL) + vecr[pl + k - 1].second << endl;
        return 0;
      }
    }
    if (x % 10 < 9 && (x < 10 || x / 10 % 10 > x % 10)) {
      vector<pair<int, int> >& vecr = r[x % 10 + 1][0];
      int pl = lower_bound(vecr.begin(), vecr.end(), make_pair(needmod, 0)) -
               vecr.begin();
      int pr =
          lower_bound(vecr.begin(), vecr.end(), make_pair(needmod + 1, 0)) -
          vecr.begin();
      if (pr - pl < k) {
        k -= pr - pl;
      } else {
        cout << (vl * 10000000LL) + vecr[pl + k - 1].second << endl;
        return 0;
      }
    }
  }
  cout << -1 << endl;
  return 0;
}