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[20];
void get1(int pos, int fst, int num, vector<int> &v) {
  if (pos < 1) {
    if (fst != 0) {
      v.push_back(num);
    }
    return;
  }
  if (fst == 0) {
    get1(pos - 1, fst, num, v);
  }
  for (int cf = 0; cf <= 9; cf++) {
    if (fst != 0) {
      if (cf == a[pos + 1]) {
        continue;
      }
      if (fst == pos + 1) {
        a[pos] = cf;
        get1(pos - 1, fst, num * 10 + cf, v);
      } else if ((a[pos + 2] - a[pos + 1]) * (cf - a[pos + 1]) > 0) {
        a[pos] = cf;
        get1(pos - 1, fst, num * 10 + cf, v);
      }
    } else if (cf > 0) {
      a[pos] = cf;
      get1(pos - 1, pos, cf, v);
    }
  }
}
const int NMAX = 1e6;
vector<pair<long long, int> > sons[2];
int main() {
  vector<int> v;
  get1(7, 0, 0, v);
  long long n, k;
  scanf("%lld %lld", &n, &k);
  for (auto it : v) {
    if (it % n == 0) {
      k--;
      if (k == 0) {
        printf("%d\n", it);
        return 0;
      }
    }
  }
  for (auto it : v) {
    if (it >= 1e6) {
      if ((it / 1000000) > (it / 100000) % 10) {
        sons[1].push_back({it % n, it});
      } else {
        sons[0].push_back({it % n, it});
      }
    } else if (it >= 1e5) {
      if (it / (100000) > (it / 10000) % 10) {
        sons[0].push_back({it % n, it});
      }
    }
  }
  sort(sons[0].begin(), sons[0].end());
  sort(sons[1].begin(), sons[1].end());
  for (auto it : v) {
    int fst = it;
    vector<int> sgn;
    if (it < 10) {
      sgn.push_back(1);
      sgn.push_back(0);
    } else {
      sgn.push_back(!(((it / 10) % 10) > (it % 10)));
    }
    long long r = (n - (1LL * it * 10000000 % n)) % n;
    for (auto wut : sgn) {
      vector<pair<long long, int> >::iterator st =
          lower_bound(sons[!wut].begin(), sons[!wut].end(), make_pair(r, 0));
      vector<pair<long long, int> >::iterator dr = lower_bound(
          sons[!wut].begin(), sons[!wut].end(), make_pair(r + 1, 0));
      if (wut == 0) {
        vector<pair<long long, int> >::iterator it2 =
            lower_bound(st, dr, make_pair(r, ((it % 10) + 1) * 1000000));
        st = it2;
      } else {
        vector<pair<long long, int> >::iterator it2 =
            lower_bound(st, dr, make_pair(r, (it % 10) * 1000000));
        dr = it2;
      }
      if (dr - st >= k) {
        while (st != dr) {
          k--;
          if (k == 0) {
            printf("%lld\n", it * 10000000LL + st->second);
            return 0;
          }
          st++;
        }
      } else {
        k -= (dr - st);
      }
    }
  }
  printf("-1\n");
  return 0;
}