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;
vector<long long> v;
long long p10[15] = {1};
long long n, k;
vector<pair<long long, pair<bool, long long> > > A, B;
bool push;
vector<bool> End;
bool start;
int len;
char s[3445];
bool check(long long n) {
  if (n < 10) return true;
  sprintf(s, "%lld", n);
  for (int i = 1; s[i] && s[i + 1]; ++i) {
    if (s[i] > s[i - 1] && s[i] > s[i + 1]) continue;
    if (s[i] < s[i - 1] && s[i] < s[i + 1]) continue;
    return false;
  }
  return true;
}
void gen(int rem, int last, bool l, long long mod, long long num, long long w,
         vector<pair<long long, pair<bool, long long> > > &X) {
  if (!rem) {
    if (push) {
      A.push_back(make_pair(mod, make_pair(start, num)));
      End.push_back(l);
      int i = 0;
      int a, b;
      int last = A[i].second.second % 10;
      if (End[i]) {
        a = lower_bound(
                B.begin(), B.end(),
                make_pair((n - A[i].first + n) % n, make_pair(false, -1ll))) -
            B.begin();
        b = lower_bound(B.begin(), B.end(),
                        make_pair((n - A[i].first + n) % n,
                                  make_pair(false, last * p10[len / 2] / 10))) -
            B.begin();
      } else {
        a = lower_bound(
                B.begin(), B.end(),
                make_pair((n - A[i].first + n) % n,
                          make_pair(true, (last + 1) * p10[len / 2] / 10))) -
            B.begin();
        b = upper_bound(B.begin(), B.end(),
                        make_pair((n - A[i].first + n) % n,
                                  make_pair(true, 1ll << 62))) -
            B.begin();
      }
      if (b - a < k) {
        k -= b - a;
      } else {
        long long Z = A[i].second.second * p10[len / 2] + B[a].second.second;
        a += k - 1;
        printf("%lld%0*lld", A[i].second.second, len / 2, B[a].second.second);
        exit(0);
      }
      A.clear();
      End.clear();
    } else
      X.push_back(make_pair(mod, make_pair(start, num)));
    v.clear();
    return;
  }
  int a, b;
  if (l)
    a = 0, b = last - 1;
  else
    a = last + 1, b = 9;
  for (int i = a; i <= b; ++i) {
    gen(rem - 1, i, !l, (mod + i * w) % n, num * 10 + i, w / 10, X);
  }
}
int main() {
  cin >> n >> k;
  long long K = k;
  for (int i = 1; i < 15; ++i) p10[i] = p10[i - 1] * 10;
  for (len = 3; len < 15; ++len) {
    if (len == 3) {
      for (int i = 1; i < p10[len]; ++i)
        if (i % n == 0 && check(i)) {
          if (i % 10 == i / 10 % 10) continue;
          --k;
          if (!k) {
            printf("%d", i);
            return 0;
          }
        }
      continue;
    }
    End.clear();
    A.clear();
    B.clear();
    push = false;
    for (int i = 0; i < 10; ++i) {
      if (len / 2 - 1 >= 0) {
        start = true;
        gen(len / 2 - 1, i, true, i * p10[len / 2 - 1] % n, i,
            p10[len / 2 - 1] / 10, B);
        start = false;
        gen(len / 2 - 1, i, false, i * p10[len / 2 - 1] % n, i,
            p10[len / 2 - 1] / 10, B);
      }
    }
    sort(B.begin(), B.end());
    push = true;
    for (int i = 1; i < 10; ++i) {
      gen((len + 1) / 2 - 1, i, true, i * p10[len - 1] % n, i,
          p10[len - 1] / 10, A);
      gen((len + 1) / 2 - 1, i, false, i * p10[len - 1] % n, i,
          p10[len - 1] / 10, A);
    }
  }
  puts("-1");
  return 0;
}