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 read() {
  long long s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
  return f * s;
}
const long long top = 100000000000000ll;
long long n, k;
bool check(long long x) {
  int lst = -1, qwq = -1, bit;
  while (x) {
    bit = x % 10, x /= 10;
    if (bit == lst) return 0;
    if (~lst && ~qwq && (bit > lst) != qwq) return 0;
    qwq = ~lst ? bit < lst : -1;
    lst = bit;
  }
  return 1;
}
int f[11][2][1000001];
vector<int> gg[5000010];
int poi, pw[10], all;
void dfs(int d, int x, int w, int s) {
  if (d == 8) {
    int val = s % n;
    all++;
    if (!f[x][w][val]) f[x][w][val] = ++poi;
    int id = f[x][w][val];
    gg[id].push_back(s);
    return;
  }
  if (d == 8) return;
  if (w)
    for (int i = 0; i < x; i++) dfs(d + 1, i, w ^ 1, s + i * pw[d]);
  else
    for (int i = x + 1; i < 10; i++) dfs(d + 1, i, w ^ 1, s + i * pw[d]);
}
void sub1() {
  for (long long i = n; i < top; i += n) {
    k -= check(i);
    if (!k) return printf("%lld\n", i), void();
  }
  return puts("-1"), void();
}
int main() {
  n = read(), k = read();
  pw[0] = 1;
  for (int i = 1; i <= 7; i++) pw[i] = 10 * pw[i - 1];
  if (n > 1000000) return sub1(), 0;
  for (long long i = n; i < 100000000ll; i += n) {
    k -= check(i);
    if (!k) return printf("%lld\n", i), 0;
  }
  dfs(0, 10, 1, 0);
  dfs(0, -1, 0, 0);
  if (k > 1ll * all * all) return puts("-1"), 0;
  for (register int i = 1; i < 1000000; i++)
    if (check(i)) {
      int wei = i % 10, w2 = i % 100 / 10, flag = (w2 > wei);
      if (i >= 10 && wei == w2) continue;
      long long val = 100000000ll * i, s = (n - val % n) % n;
      for (register int b = 0; b < 10; b++)
        if (b != wei) {
          int ty = b > wei;
          if (i < 10 || flag == ty) {
            int pos = f[b][ty][s];
            if (!pos) continue;
            if (k <= gg[pos].size()) {
              sort(gg[pos].begin(), gg[pos].end());
              return printf("%lld\n", val + gg[pos][k - 1]), 0;
            } else
              k -= gg[pos].size();
          }
        }
    }
  puts("-1");
  return 0;
}