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 INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
ostream &operator<<(ostream &o, const vector<T> &t) {
  o << '[';
  for (__typeof((t).begin()) i = (t).begin(); i != (t).end(); ++i) {
    if (i != t.begin()) o << ',';
    o << *i;
  }
  return o << ']';
}
template <class S, class T>
ostream &operator<<(ostream &o, const pair<S, T> &t) {
  return o << '(' << t.first << ',' << t.second << ')';
}
template <int N, class Tp>
void output(ostream &, const Tp &) {}
template <int N, class Tp, class, class... Ts>
void output(ostream &o, const Tp &t) {
  if (N) o << ',';
  o << get<N>(t);
  output<N + 1, Tp, Ts...>(o, t);
}
template <class... Ts>
ostream &operator<<(ostream &o, const tuple<Ts...> &t) {
  o << '(';
  output<0, tuple<Ts...>, Ts...>(o, t);
  return o << ')';
}
template <class T>
void output(T t, char z = 10) {
  if (t < 0) t = -t, putchar(45);
  int c[20];
  int k = 0;
  while (t) c[k++] = t % 10, t /= 10;
  for (k || (c[k++] = 0); k;) putchar(c[--k] ^ 48);
  putchar(z);
}
template <class T>
void outputs(T t) {
  output(t);
}
template <class S, class... T>
void outputs(S a, T... t) {
  output(a, 32);
  outputs(t...);
}
template <class T>
void output(T *a, int n) {
  for (int i = 0; i < (int)(n); ++i) output(a[i], i != n - 1 ? ',' : 10);
}
template <class T>
void output(T *a, int n, int m) {
  for (int i = 0; i < (int)(n); ++i) output(a[i], m);
}
template <class T>
bool input(T &t) {
  int n = 1, c;
  for (t = 0; !isdigit(c = getchar()) && ~c && c - 45;)
    ;
  if (!~c) return 0;
  for (c - 45 && (n = 0, t = c ^ 48); isdigit(c = getchar());)
    t = 10 * t + c - 48;
  t = n ? -t : t;
  return 1;
}
template <class S, class... T>
bool input(S &a, T &...t) {
  input(a);
  return input(t...);
}
bool wavy2(long long x) {
  int a = x % 10;
  int b = x / 10 % 10;
  x /= 100;
  while (x) {
    int c = x % 10;
    if ((b > c && b > a) || (b < c && b < a)) {
    } else {
      return 0;
    }
    tie(a, b) = make_tuple(b, c);
    x /= 10;
  }
  return 1;
}
vector<int> wavies;
void dfs(int cur, int val, int pre, int flag) {
  if (cur == 8) {
    if (val) wavies.push_back(val);
    return;
  }
  if (flag == 0) {
    for (int i = 0; i < (int)(10); ++i) {
      dfs(cur + 1, val * 10 + i, i, i != 0);
    }
  } else if (flag == 1) {
    for (int i = 0; i < (int)(10); ++i) {
      if (pre != i) {
        dfs(cur + 1, val * 10 + i, i, i < pre ? 2 : 3);
      }
    }
  } else if (flag == 2) {
    for (int i = pre + 1; i <= 9; ++i) {
      dfs(cur + 1, val * 10 + i, i, 3);
    }
  } else if (flag == 3) {
    for (int i = 0; i < pre; ++i) {
      dfs(cur + 1, val * 10 + i, i, 2);
    }
  }
}
int num[1000000][10][2];
long long solve(long long n, long long k) {
  long long cnt = 0;
  for (int x : wavies) {
    if (x >= 1000000) break;
    if (x % n == 0) {
      cnt++;
      if (cnt == k) {
        return x;
      }
    }
  }
  memset(num, 0, sizeof(num));
  for (int x : wavies) {
    if (x >= 1000000) break;
    if (x < 10000) continue;
    int a = x / 100000;
    int b = x / 10000 % 10;
    if (a != b) {
      if (a == 0 && b <= (x / 1000) % 10) continue;
      num[x % n][a][a < b]++;
    }
  }
  for (long long x : wavies) {
    long long tmp = 0;
    long long md = (n - x * 1000000 % n) % n;
    if (md >= 1000000) continue;
    if (x < 10) {
      for (int i = 0; i < (int)(10); ++i) {
        if (x == i) continue;
        tmp += num[md][i][i < x];
      }
    } else {
      int a = x % 10;
      int b = x / 10 % 10;
      if (a < b) {
        for (int i = a + 1; i < 10; ++i) {
          tmp += num[md][i][0];
        }
      } else {
        for (int i = 0; i < a; ++i) {
          tmp += num[md][i][1];
        }
      }
    }
    if (cnt + tmp >= k) {
      for (int y : wavies) {
        long long t = x * 1000000 + y;
        if (wavy2(t) && t % n == 0) {
          cnt++;
          if (cnt == k) {
            return x * 1000000 + y;
          }
        }
      }
    }
    cnt += tmp;
  }
  return -1;
}
int main() {
  dfs(0, 0, -1, 0);
  long long n, k;
  while (cin >> n >> k) {
    cout << solve(n, k) << endl;
  }
}