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;
const int N = 1e7;
const long long inf = 1e14;
inline void get(int &x) {
  char ch = getchar();
  x = 0;
  while (ch < '0') ch = getchar();
  while (ch >= '0') x = x * 10 + ch - '0', ch = getchar();
}
long long n, m, val[N];
int tt, ver[N], nxt[N], head[N];
int tot, f[10], sum[N], cnt[15][15];
inline int cmp(int a, int b) { return (a == b) ? 0 : ((a > b) ? 1 : -1); }
void dfs(int p, int n) {
  if (p > n) {
    if (n == 2 && f[1] == f[2]) return;
    tot++;
    for (int i = 1; i <= n; i++) val[tot] = val[tot] * 10 + f[i];
    return;
  }
  for (int i = 0; i <= 9; i++) {
    f[p] = i;
    if (p >= 3 && (!cmp(f[p - 2], f[p - 1]) ||
                   cmp(f[p], f[p - 1]) != cmp(f[p - 2], f[p - 1])))
      continue;
    dfs(p + 1, n);
  }
}
inline void add(int x, int y) {
  ver[++tt] = y, nxt[tt] = head[x], head[x] = tt;
}
inline void ycl() {
  for (int i = 1; i <= 7; i++)
    for (f[1] = 1; f[1] <= 9; f[1]++) dfs(2, i);
}
inline bool check(long long p) {
  int zc = 0, st[20];
  for (; p; p /= 10) st[++zc] = p % 10;
  for (int i = 2; i <= zc - 1; i++)
    if (!cmp(st[i], st[i - 1]) ||
        cmp(st[i], st[i - 1]) != cmp(st[i], st[i + 1]))
      return 0;
  return 1;
}
int main() {
  ycl();
  cin >> n >> m;
  if (n > N) {
    for (long long i = n; i <= inf; i += n)
      if (check(i) && --m == 0) {
        cout << i << endl;
        return 0;
      }
    puts("-1");
    return 0;
  } else {
    for (int i = 1; i <= tot; i++)
      if (val[i] % n == 0 && --m == 0) {
        cout << val[i] << endl;
        return 0;
      }
    for (int i = tot; i >= 1; i--) add(val[i] % n, i);
    for (int i = 0; i <= n - 1; i++)
      if (head[i]) {
        int v = (n - (long long)i * N % n) % n;
        if (!head[v]) continue;
        memset(cnt, 0, sizeof(cnt));
        for (int j = head[v]; j; j = nxt[j]) {
          int t = val[ver[j]];
          if (t > N / 10)
            cnt[t / (N / 10)][t / (N / 100) % 10]++;
          else if (t > N / 100 && t / (N / 1000) % 10 < t / (N / 100) % 10)
            cnt[0][t / (N / 100) % 10]++;
        }
        for (int j = head[i]; j; j = nxt[j]) {
          int p = ver[j], a = val[p] % 10, b = val[p] / 10 % 10;
          if (val[p] < 10) {
            for (int t1 = a + 1; t1 <= 9; t1++)
              for (int t2 = t1 - 1; t2 >= 0; t2--) sum[p] += cnt[t1][t2];
            for (int t1 = a - 1; t1 >= 0; t1--)
              for (int t2 = t1 + 1; t2 <= 9; t2++) sum[p] += cnt[t1][t2];
          } else if (b > a)
            for (int t1 = a + 1; t1 <= 9; t1++)
              for (int t2 = t1 - 1; t2 >= 0; t2--) sum[p] += cnt[t1][t2];
          else
            for (int t1 = a - 1; t1 >= 0; t1--)
              for (int t2 = t1 + 1; t2 <= 9; t2++) sum[p] += cnt[t1][t2];
        }
      }
    for (int i = 1; i <= tot; i++) {
      if (m > sum[i])
        m -= sum[i];
      else {
        for (int j = 1; j <= tot; j++)
          if ((val[i] * N + val[j]) % n == 0 && check(val[i] * N + val[j]) &&
              --m == 0) {
            if (val[i] * N + val[j] > inf)
              puts("-1");
            else
              printf("%I64d%07I64d\n", val[i], val[j]);
            return 0;
          }
      }
    }
  }
  puts("-1");
}