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 xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
int dem;
long long n, k;
struct re {
  int m, x, t, v;
};
re c[int(1e6 + 100)];
bool cmp(re a, re b) {
  if (a.m < b.m || (a.m == b.m && a.t < b.t) ||
      (a.m == b.m && a.t == b.t && a.x < b.x))
    return true;
  return false;
}
bool cmp2(re a, re b) {
  if (a.m < b.m || (a.m == b.m && a.t < b.t) ||
      (a.m == b.m && a.t == b.t && a.x < b.x) ||
      (a.m == b.m && a.t == b.t && a.x == b.x && a.v < b.v))
    return true;
  return false;
}
int fleft(int t, int m, int x) {
  re a;
  a.t = t;
  a.m = m;
  a.x = x;
  int l = 1, r = dem;
  int res = dem + 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (!cmp(c[mid], a)) {
      r = mid - 1;
      res = mid;
    } else
      l = mid + 1;
  }
  return res;
}
int fright(int t, int m, int x) {
  re a;
  a.t = t;
  a.m = m;
  a.x = x;
  int l = 1, r = dem;
  int res = 0;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (!cmp(a, c[mid])) {
      l = mid + 1;
      res = mid;
    } else
      r = mid - 1;
  }
  return res;
}
int check(int x, int d = 0) {
  int n = 0;
  int a[15];
  while (x != 0) {
    n++;
    a[n] = x % 10;
    x /= 10;
  }
  if (d != 0) {
    while (n < d) {
      n++;
      a[n] = 0;
    }
  }
  if (n == 1) return 1;
  int m;
  if (a[2] > a[1])
    m = 2;
  else if (a[2] < a[1])
    m = 1;
  else
    return 0;
  for (int i = (3), _b = (n); i <= _b; i++) {
    int m2;
    if (a[i] > a[i - 1])
      m2 = 2;
    else if (a[i] < a[i - 1])
      m2 = 1;
    else
      return 0;
    if (m2 == m) return 0;
    m = m2;
  }
  if (a[n - 1] > a[n])
    return 2;
  else
    return 1;
}
int main() {
  scanf("%I64d%I64d", &n, &k);
  long long d = 0;
  for (int i = (1), _b = (int(1e7) - 1); i <= _b; i++)
    if (i % n == 0 && check(i)) {
      d++;
      if (d == k) {
        cout << i << endl;
        return 0;
      }
    }
  for (int i = (int(1e5)), _b = (int(1e7) - 1); i <= _b; i++) {
    int t = check(i, 7);
    if (!t) continue;
    dem++;
    c[dem].m = i % n;
    c[dem].t = t - 1;
    c[dem].x = i / (int)(1e6);
    c[dem].v = i;
  }
  sort(c + 1, c + 1 + dem, cmp2);
  for (int i = (1), _b = (int(1e7) - 1); i <= _b; i++)
    if (check(i)) {
      int x = i % 10;
      int z = -1;
      if (i / 10 != 0) z = (i / 10) % 10;
      long long m;
      m = (n - (i * (long long)(1e7)) % n) % n;
      if (m > int(1e8)) continue;
      if (z == -1 || x > z)
        if (x != 0) {
          int l = fleft(1, m, 0);
          int r = fright(1, m, x - 1);
          if (d + r - l + 1 >= k) {
            for (int j = (l), _b = (r); j <= _b; j++) {
              d++;
              if (d == k) {
                cout << i * (long long)(1e7) + c[j].v << endl;
                return 0;
              }
            }
          }
          if (r - l + 1 >= 0) d += r - l + 1;
        }
      if (z == -1 || x < z)
        if (x != 9) {
          int l = fleft(0, m, x + 1);
          int r = fright(0, m, 9);
          if (d + r - l + 1 >= k) {
            for (int j = (l), _b = (r); j <= _b; j++) {
              d++;
              if (d == k) {
                cout << i * (long long)(1e7) + c[j].v << endl;
                return 0;
              }
            }
          }
          if (r - l + 1 >= 0) d += r - l + 1;
        }
    }
  cout << -1 << endl;
}