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>
const int inf = 1e9 + 7;
const int OO = 0;
using namespace std;
const long long lim = 1e14, hlim = 1e7;
const int lo = 2e6;
int dig[15], len;
int W[1000000], nxt = 0;
void con(long long x) {
  len = 0;
  while (x) {
    dig[len++] = x % 10;
    x /= 10;
  }
  reverse(dig, dig + len);
}
bool wavy(long long x) {
  if (x < 10) return true;
  int f, l, dir;
  l = x % 10, x /= 10;
  f = x % 10, x /= 10;
  if (f == l) return false;
  if (f < l)
    dir = 0;
  else
    dir = 1;
  while (x) {
    l = f;
    f = x % 10, x /= 10;
    if (dir && f >= l)
      return false;
    else if (!dir && f <= l)
      return false;
    dir ^= 1;
  }
  return true;
}
bool realwavy(long long x) {
  if (10 <= x && x < 100 && x / 10 == x % 10) return false;
  con(x);
  for (int i = 1; i < len - 1; i++)
    if (dig[i - 1] == dig[i] || dig[i] == dig[i + 1] ||
        (dig[i - 1] <= dig[i] && dig[i] <= dig[i + 1]) ||
        (dig[i - 1] >= dig[i] && dig[i] >= dig[i + 1]))
      return false;
  return true;
}
long long pw[15], n, k;
int S[lo][10][2] = {};
void calc() {
  for (int i = 1; i < hlim; i++) {
    if (wavy(i)) {
      W[nxt++] = i;
      if (i % n == 0) k--;
      if (k == 0) {
        cout << i << '\n';
        cin.ignore(), cin.get();
        exit(0);
      }
      if (i >= hlim / 100) {
        con(i);
        if (len == 6 && dig[0] > dig[1]) {
          S[i % n][0][1]++;
        } else if (len == 7) {
          if (dig[0] < dig[1])
            S[i % n][dig[0]][1]++;
          else
            S[i % n][dig[0]][0]++;
        }
      }
    }
  }
  for (int i = 0; i < lo; i++) {
    for (int j = 1; j < 10; j++) S[i][j][1] += S[i][j - 1][1];
    for (int j = 8; j >= 0; j--) S[i][j][0] += S[i][j + 1][0];
  }
}
int brute(int k) {
  for (int i = 1;; i++) {
    if (wavy(i)) k--;
    if (!k) return i;
  }
}
int realbrute(int k) {
  for (int i = 1;; i++) {
    if (realwavy(i)) k--;
    if (!k) return i;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  pw[0] = 1;
  for (int i = 1; i < 15; i++) pw[i] = 10LL * pw[i - 1];
  cin >> n >> k;
  if (n > lim / k) {
    cout << -1;
    cin.ignore(), cin.get();
    return 0;
  }
  if (n >= lo) {
    for (long long i = n; i <= lim; i += n) {
      if (wavy(i)) k--;
      if (!k) {
        cout << i << '\n';
        cin.ignore(), cin.get();
        return 0;
      }
    }
    cout << -1;
    cin.ignore(), cin.get();
    return 0;
  }
  if (n < 10 && n * k < 10) {
    cout << n * k << '\n';
    cin.ignore(), cin.get();
    return 0;
  }
  calc();
  long long start = -1;
  for (int ii = 0; ii < nxt; ii++) {
    long long i = W[ii];
    con(i);
    long long mneed = (-i * 10000000 % n + n) % n;
    int cur = 0;
    if ((len == 1 && i > 0) || dig[len - 2] < dig[len - 1])
      cur += S[mneed][dig[len - 1] - 1][1];
    if ((len == 1 && i < 9) || (len > 1 && dig[len - 2] > dig[len - 1]))
      cur += S[mneed][dig[len - 1] + 1][0];
    if (OO)
      cout << "for start " << i << ", need mod " << mneed << ". there are "
           << cur << '\n';
    if (OO) cout << "current k " << k << '\n';
    if (cur >= k) {
      start = i;
      break;
    }
    k -= cur;
  }
  if (start == -1) {
    cout << -1;
    cin.ignore(), cin.get();
    return 0;
  }
  for (int i = hlim / 100; i < hlim; i++) {
    long long val = start * 10000000 + i;
    if (val % n == 0 && wavy(val)) {
      k--;
      if (k == 0) {
        cout << val << '\n';
        cin.ignore(), cin.get();
        return 0;
      }
    }
  }
  cout << "error\n";
  cin.ignore();
  cin.get();
}