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;
int wavy(long long int x) {
  int la = -1, th = -1, sg = 0;
  while (x) {
    la = th;
    th = x % 10;
    x /= 10;
    if (la == -1) continue;
    if (la == th) return 0;
    if (sg == 0) {
      if (la > th)
        sg = 1;
      else
        sg = -1;
    } else {
      if (sg == 1 && la < th) return 0;
      if (sg == -1 && la > th) return 0;
    }
    sg *= -1;
  }
  return 1;
}
int wavy1(long long int x) {
  int la = -1, th = -1, sg = -1;
  while (x) {
    la = th;
    th = x % 10;
    x /= 10;
    if (la == -1) continue;
    if (la == th) return 0;
    if (sg == 1 && la < th) return 0;
    if (sg == -1 && la > th) return 0;
    sg *= -1;
  }
  return 1;
}
int wavy2(long long int x) {
  int la = -1, th = -1, sg = 1;
  while (x) {
    la = th;
    th = x % 10;
    x /= 10;
    if (la == -1) continue;
    if (la == th) return 0;
    if (sg == 1 && la < th) return 0;
    if (sg == -1 && la > th) return 0;
    sg *= -1;
  }
  return 1;
}
long long int n, k;
void case1() {
  long long int i;
  for (i = n; i <= 1e14; i += n) {
    if (wavy(i)) k--;
    if (k == 0) {
      cout << i;
      exit(0);
    }
  }
  cout << -1;
  exit(0);
}
int cnt[1000002][10][2];
int f[800700][2];
int tot;
void swap(int l, int r) {
  int t;
  t = f[l][0];
  f[l][0] = f[r][0];
  f[r][0] = t;
  t = f[l][1];
  f[l][1] = f[r][1];
  f[r][1] = t;
}
void qsort(int l, int r) {
  int i = l, j = r, mid = f[rand() % (r - l + 1) + l][0] % n;
  while (i <= j) {
    for (; (f[i][0] % n) < mid; i++)
      ;
    for (; (f[j][0] % n) > mid; j--)
      ;
    if (i <= j) swap(i++, j--);
  }
  if (l < j) qsort(l, j);
  if (i < r) qsort(i, r);
}
bool Wavy1[10020000], Wavy2[10020000];
void case2_prepare() {
  int i, c0, c1;
  for (i = 1000000; i < 10000000; i++) {
    c0 = c1 = 0;
    if (Wavy1[i]) c0 = 1;
    if (Wavy2[i]) c1 = 1;
    if (c0 || c1) f[++tot][0] = i, f[tot][1] = 0;
    if (c0) f[tot][1] |= 1;
    if (c1) f[tot][1] |= 2;
  }
  for (i = 100000; i < 1000000; i++)
    if (Wavy1[i]) f[++tot][0] = i, f[tot][1] = 1;
  qsort(1, tot);
}
void case3_prepare() {
  int i, c0, c1, j;
  for (i = 1000000; i < 10000000; i++) {
    c0 = c1 = 0;
    j = i % n;
    if (Wavy1[i]) cnt[j][i / 1000000][0]++;
    if (Wavy2[i]) cnt[j][i / 1000000][1]++;
  }
  for (i = 100000; i < 1000000; i++)
    if (Wavy1[i]) cnt[i % n][0][0]++;
  for (i = 0; i < n; i++)
    for (j = 1; j < 10; j++)
      cnt[i][j][0] += cnt[i][j - 1][0], cnt[i][j][1] += cnt[i][j - 1][1];
}
int Fdayu(int i, int j, int k) {
  if (n < 1000000) return cnt[i][9][k - 1] - cnt[i][j][k - 1];
  int l = 1, r = tot, mid, ans = 0;
  while (r - l > 1) {
    mid = (l + r) >> 1;
    if (f[mid][0] % n < i)
      l = mid;
    else
      r = mid;
  }
  if (f[l][0] % n == i)
    mid = l;
  else
    mid = r;
  while (f[mid][0] % n == i) {
    if (f[mid][0] / 1000000 > j)
      if (k == 1) {
        if (f[mid][1] & 1) ans++;
      } else if (f[mid][1] & 2)
        ans++;
    mid++;
  }
  return ans;
}
int Fxiaoyu(int i, int j, int k) {
  if (n < 1000000) {
    if (j > 0)
      return cnt[i][j - 1][k - 1];
    else
      return 0;
  }
  int l = 1, r = tot, mid, ans = 0;
  while (r - l > 1) {
    mid = (l + r) >> 1;
    if (f[mid][0] % n < i)
      l = mid;
    else
      r = mid;
  }
  if (f[l][0] % n == i)
    mid = l;
  else
    mid = r;
  while (f[mid][0] % n == i) {
    if (f[mid][0] / 1000000 < j)
      if (k == 1) {
        if (f[mid][1] & 1) ans++;
      } else if (f[mid][1] & 2)
        ans++;
    mid++;
  }
  return ans;
}
void get_final(long long int a) {
  long long int i, j;
  for (i = 100000; i < 10000000; i++)
    if ((Wavy1[i] || Wavy2[i])) {
      j = a * 10000000 + i;
      if (j % n == 0) {
        if (wavy(j)) k--;
        if (k == 0) {
          cout << j;
          exit(0);
        }
      }
    }
}
void calc() {
  long long int a, b, c, lk;
  for (long long int i = n; i <= 10000000; i += n) {
    if ((Wavy1[i] || Wavy2[i])) k--;
    if (k == 0) {
      cout << i;
      return;
    }
  }
  for (a = 1; a <= 10000000; a++) {
    if (!(Wavy1[a] || Wavy2[a])) continue;
    lk = k;
    c = n - (10000000 * a) % n;
    if (c == n) c = 0;
    if (((a % 100) / 10) > (a % 10) || a < 10) k -= Fdayu(c, a % 10, 2);
    if (((a % 100) / 10) < (a % 10) || a < 10) k -= Fxiaoyu(c, a % 10, 1);
    if (k <= 0) k = lk, get_final(a);
  }
  cout << -1;
}
int main() {
  int i, s = 0;
  for (i = 1; i <= 10000000; i++) {
    if (wavy1(i)) Wavy1[i] = 1;
    if (wavy2(i)) Wavy2[i] = 1;
  }
  cin >> n >> k;
  if (n >= 10000000) case1();
  if (n >= 1000000)
    case2_prepare();
  else
    case3_prepare();
  calc();
  return 0;
}