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 a[55];
vector<int> small;
long long n, k;
vector<pair<int, long long> > first;
vector<pair<int, int> > w[10][2];
bool good(int a, int b, int c) {
  if (b > a && b > c) return true;
  if (b < a && b < c) return true;
  return false;
}
void go(int cur, int num) {
  if (cur > 0 && num % n == 0) {
    small.push_back(num);
  }
  if (cur == 7) return;
  for (int d = 0; d < 10; ++d) {
    if (cur == 0 && d == 0) continue;
    if (cur > 0 && a[cur - 1] == d) continue;
    if (cur > 1 && !good(a[cur - 2], a[cur - 1], d)) continue;
    a[cur] = d;
    go(cur + 1, num * 10 + d);
  }
}
void goF(int cur, int num) {
  if (cur > 0) {
    first.push_back(make_pair(num, (1LL * num * 10000000) % n));
  }
  if (cur == 7) return;
  for (int d = 0; d < 10; ++d) {
    if (cur == 0 && d == 0) continue;
    if (cur > 0 && a[cur - 1] == d) continue;
    if (cur > 1 && !good(a[cur - 2], a[cur - 1], d)) continue;
    a[cur] = d;
    goF(cur + 1, num * 10 + d);
  }
}
void goS(int cur, int num) {
  if (cur == 7) {
    w[a[0]][a[0] < a[1]].push_back(make_pair(num % n, num));
    return;
  }
  for (int d = 0; d < 10; ++d) {
    if (cur > 0 && a[cur - 1] == d) continue;
    if (cur > 1 && !good(a[cur - 2], a[cur - 1], d)) continue;
    a[cur] = d;
    goS(cur + 1, num * 10 + d);
  }
}
int get_lower(vector<pair<int, int> > &a, pair<int, int> val) {
  int l, r;
  l = 0;
  r = a.size();
  while (l + 1 < r) {
    int c = (l + r) / 2;
    if (a[c] >= val)
      r = c;
    else
      l = c;
  }
  return l;
}
int get_higher(vector<pair<int, int> > &a, pair<int, int> val) {
  int l, r;
  l = -1;
  r = a.size() - 1;
  while (l + 1 < r) {
    int c = (l + r) / 2;
    if (a[c] < val)
      l = c;
    else
      r = c;
  }
  return r;
}
int main() {
  cin >> n >> k;
  go(0, 0);
  if (k <= small.size()) {
    sort(small.begin(), small.end());
    cout << small[k - 1] << endl;
    return 0;
  }
  k -= small.size();
  goF(0, 0);
  goS(0, 0);
  for (int i = 0; i < 10; ++i)
    for (int j = 0; j < 2; ++j)
      if (w[i][j].size()) sort(w[i][j].begin(), w[i][j].end());
  sort(first.begin(), first.end());
  for (int i = 0; i < first.size(); ++i) {
    pair<int, long long> tmp = first[i];
    int len = 0;
    if (tmp.first > 9) a[len++] = tmp.first / 10 % 10;
    a[len++] = tmp.first % 10;
    long long need = (n - tmp.second) % n;
    if (need < 0) need += n;
    if (need > 10000000) continue;
    for (int d = 0; d < 10; ++d) {
      if (len > 0 && a[len - 1] == d) continue;
      if (len > 1 && !good(a[len - 2], a[len - 1], d)) continue;
      bool dr = false;
      if (a[len - 1] > d) dr = true;
      if (w[d][dr].size() == 0) continue;
      int it1 = get_higher(w[d][dr], make_pair(need, 0));
      int it2 = get_lower(w[d][dr], make_pair(need, 1000000000));
      if (w[d][dr][it1].first != need) continue;
      int have = it2 - it1 + 1;
      if (have < k)
        k -= have;
      else {
        long long ret = first[i].first;
        ret = ret * 10000000 + w[d][dr][it1 + k - 1].second;
        cout << ret << endl;
        return 0;
      }
    }
  }
  cout << -1 << endl;
  return 0;
}