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>
void read(T& x) {
  char c;
  bool f = 0;
  for (c = getchar(); c <= 32; c = getchar())
    ;
  if (c == '-') c = getchar(), f = 1;
  for (x = 0; c > 32; c = getchar()) x = x * 10 + (c - '0');
  if (f) x = -x;
}
const long long L = int(1e7);
long long n, k;
int l, p, totm;
int tt[21], ten[21];
vector<int> H, D;
map<int, int> M;
int g[2000010][10][2];
inline int W(int s, int x) { return ((s) / ten[(x)-1]) % 10; }
inline bool pd(int a, int x, int y) {
  return ((a) < min(x, y) || (a) > max(x, y));
}
bool check(long long x) {
  int i, w = 0;
  for (; x; x /= 10) tt[++w] = x % 10;
  for (i = (2); i <= (w - 1); i++)
    if (!pd(tt[i], tt[i - 1], tt[i + 1])) return 0;
  return 1;
}
inline bool PP(long long x) {
  if (x >= 10 && x <= 99) return x % 11 > 0;
  return 1;
}
void dfs(int d, int s) {
  if (s)
    if (PP(s)) H.push_back(s);
  if (d <= 7)
    for (int i = 0; i <= 9; i++)
      if (s || i)
        if (s < 10 || pd(s % 10, s / 10 % 10, i)) dfs(d + 1, s * 10 + i);
}
void go(int d, int s) {
  for (int i = 0; i <= 9; i++)
    if (d <= 2 || pd(W(s, d - 1), W(s, d - 2), i)) {
      if (d == 7) {
        int op = (s + int(1e6) * i) % n;
        D.push_back(s + int(1e6) * i);
        if (M.find(op) == M.end()) M[op] = ++totm;
        g[M[op]][i][i < W(s, d - 1)]++;
      } else
        go(d + 1, s + ten[d - 1] * i);
    }
}
int main() {
  cin >> n >> k;
  ten[0] = 1;
  for (int i = 1; i <= 18; i++) ten[i] = ten[i - 1] * 10;
  if (n >= L) {
    for (long long i = n; i <= L * L; i += n)
      if (check(i) && (--k == 0)) {
        cout << i << endl;
        return 0;
      }
    cout << -1 << endl;
    return 0;
  }
  dfs(1, 0);
  sort(H.begin(), H.end());
  go(1, 0);
  sort(D.begin(), D.end());
  for (int i = 0; i < H.size(); i++)
    if (H[i] % n == 0)
      if (--k == 0) {
        cout << H[i] << endl;
        return 0;
      }
  long long base = L % n;
  for (int i = 0; i < H.size(); i++) {
    int op, op2 = (n - 1LL * H[i] * base % n) % n;
    if (M.find(op2) == M.end()) continue;
    op = M[op2];
    for (int j = 0; j <= 9; j++)
      if (j != H[i] % 10 && (H[i] < 10 || pd(H[i] % 10, H[i] / 10 % 10, j))) {
        int r = g[op][j][(H[i] % 10) > j];
        if (r >= k) {
          int dd = 0;
          for (int t = 0; t < D.size(); t++)
            if ((1LL * H[i] * L + D[t]) % n == 0 && W(D[t], 7) == j &&
                (W(D[t], 7) < W(D[t], 6)) == ((H[i] % 10) > j))
              if (--k == 0) {
                cout << 1LL * H[i] * L + D[t] << endl;
                return 0;
              }
        } else
          k -= r;
      }
  }
  cout << -1 << endl;
  return 0;
}