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;
long long int k, n;
int a[7];
int q[1000000];
int quantity = 0;
long long int res = -1;
map<int, list<int> > mods2;
map<int, int> sizes;
list<int>::iterator it;
bool sizes2[10000000];
int inline key(int mod, int first_digit, bool isSecondMore) {
  return mod * 100 + (10 * isSecondMore + first_digit);
}
void addNumber(int level) {
  int ch = 0;
  for (int i = 0; i <= level; i++) ch = ch * 10 + a[i];
  q[quantity] = ch;
  if (level == 5 && a[0] > a[1]) {
    mods2[key(q[quantity] % n, 0, true)].push_back(q[quantity]);
    sizes[key(q[quantity] % n, 0, true)]++;
    sizes2[q[quantity] % n]++;
  } else if (level == 6) {
    mods2[key(q[quantity] % n, a[0], a[0] < a[1])].push_back(q[quantity]);
    sizes[key(q[quantity] % n, a[0], a[0] < a[1])]++;
    sizes2[q[quantity] % n]++;
  }
  quantity++;
}
void inline ciklDown(int level, int cur);
void inline ciklUp(int level, int cur) {
  for (a[cur] = a[cur - 1] + 1; a[cur] < 10; a[cur]++)
    if (cur == level)
      addNumber(level);
    else
      ciklDown(level, cur + 1);
}
void inline ciklDown(int level, int cur) {
  for (a[cur] = 0; a[cur] < a[cur - 1]; a[cur]++)
    if (cur == level)
      addNumber(level);
    else
      ciklUp(level, cur + 1);
}
void inline cikl(int level, int cur) {
  for (a[cur] = cur == 0 ? 1 : 0; a[cur] < 10; a[cur]++)
    if (cur == level)
      addNumber(level);
    else if (cur == 0) {
      ciklDown(level, cur + 1);
      ciklUp(level, cur + 1);
    } else if (a[cur] > a[cur - 1])
      ciklDown(level, cur + 1);
    else if (a[cur] < a[cur - 1])
      ciklUp(level, cur + 1);
}
long long int pereborOstatkov(long long int needMod, int start, int finish,
                              bool isSecondMore, long long int left) {
  if (needMod >= 10000000 || !sizes2[needMod]) return 0;
  for (int dig = start; dig < finish; dig++) {
    int size1 = sizes[key(needMod, dig, isSecondMore)];
    if (k > size1)
      k -= size1;
    else {
      for (it = mods2[key(needMod, dig, isSecondMore)].begin(); k > 0; ++it)
        k--;
      it--;
      return left * 10000000 + *it;
    }
  }
  return 0;
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < 7; i++) cikl(i, 0);
  if (n % 100 == 0) {
    cout << -1;
    return 0;
  }
  int i;
  for (i = 0; i < quantity && k > 0; i++)
    if (q[i] % n == 0) k--;
  if (!k) {
    cout << q[i - 1];
    return 0;
  }
  for (i = 0; i < 9; i++) {
    long long int needMod = (n - ((long long int)q[i] * 10000000 % n)) % n;
    int l_last = q[i] % 10;
    res = pereborOstatkov(needMod, 0, l_last, true, q[i]);
    if (res) {
      cout << res;
      return 0;
    }
    res = pereborOstatkov(needMod, l_last + 1, 10, false, q[i]);
    if (res) {
      cout << res;
      return 0;
    }
  }
  for (i = 9; i < quantity && k > 0; i++) {
    long long int needMod = (n - ((long long int)q[i] * 10000000 % n)) % n;
    int l_last = q[i] % 10;
    int l_prev = (q[i] / 10) % 10;
    int start = 0, finish = l_last;
    if (l_last < l_prev) {
      start = l_last + 1;
      finish = 10;
    }
    res = pereborOstatkov(needMod, start, finish, l_last > l_prev, q[i]);
    if (res) {
      cout << res;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}