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 Maxn = 20;
long long pw[Maxn];
int arr[Maxn];
vector<long long> wave;
int ed = 0;
vector<int> s[2][10];
void get_arr(int n, int k) {
  for (int i = 0; i < n; i++) arr[n - i - 1] = k % 10, k /= 10;
}
bool is_wavy(int n, int k) {
  for (int i = 0; i < n; i++) arr[n - i - 1] = k % 10, k /= 10;
  for (int i = 1; i < n; i++)
    if (arr[i] == arr[i - 1]) return 0;
  for (int i = 1; i < n - 1; i++) {
    if ((arr[i - 1] < arr[i]) == (arr[i] < arr[i + 1])) return 0;
  }
  return 1;
}
long long t = 0;
long long go(long long n, long long Mod, long long k) {
  if (n <= 7) {
    long long cnt = 0;
    for (int i = pw[n - 1]; i < pw[n]; i++) {
      if (i % Mod == 0 && is_wavy(n, i)) k--, cnt++;
      if (!k) return i;
    }
    return -cnt;
  }
  long long m = n - 7;
  n = 7;
  vector<int> v;
  long long res = 0;
  for (int i = pw[m - 1]; i < pw[m]; i++)
    if (is_wavy(m, i)) v.push_back(i);
  res = 0;
  long long last = 0;
  for (int j = 0; j < v.size(); j++) {
    get_arr(m, v[j]);
    last = res;
    for (int i = 0; i < 10; i++)
      if (i != arr[m - 1])
        if (m == 1 || (i > arr[m - 1]) == (arr[m - 2] > arr[m - 1])) {
          if ((Mod - (((long long)v[j] * pw[7]) % Mod)) % Mod >= 1e7) continue;
          int l =
              lower_bound(
                  s[(i > arr[m - 1])][i].begin(), s[(i > arr[m - 1])][i].end(),
                  int((Mod - (((long long)v[j] * pw[7]) % Mod)) % Mod)) -
              s[(i > arr[m - 1])][i].begin();
          int r =
              upper_bound(
                  s[(i > arr[m - 1])][i].begin(), s[(i > arr[m - 1])][i].end(),
                  int((Mod - (((long long)v[j] * pw[7]) % Mod)) % Mod)) -
              s[(i > arr[m - 1])][i].begin();
          res += r - l;
        }
    if (res >= k) {
      for (int r = 0; r < wave.size(); r++) {
        long long x = wave[r];
        if ((x + (long long)v[j] * pw[7]) % Mod) continue;
        get_arr(n, x);
        int i = arr[0];
        int c = (arr[0] > arr[1]);
        get_arr(m, v[j]);
        if (arr[m - 1] == i) continue;
        if (((arr[m - 1] < i) == c) &&
            (m == 1 || (arr[m - 1] < arr[m - 2]) == c)) {
          if (++last == k) {
            return x + (long long)v[j] * pw[7];
          }
        }
      }
    }
  }
  return -res;
}
int main() {
  long long n, k;
  cin >> n >> k;
  pw[0] = 1;
  for (int i = 1; i <= 14; i++) pw[i] = pw[i - 1] * 10;
  for (int i = 0; i < 1e7; i++) {
    if (is_wavy(7, i)) {
      s[(arr[0] > arr[1])][arr[0]].push_back(i % n);
      wave.push_back(i);
    }
  }
  if (n < 1e7)
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 10; j++) sort(s[i][j].begin(), s[i][j].end());
  int cnt = 0;
  for (int i = 1; i <= 14; i++) {
    long long x = go(i, n, k);
    if (x <= 0)
      k += x;
    else {
      cout << x << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}