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 mid = 10000000;
int fx(long long x) { return x < 0 ? -1 : x > 0; }
int isnumber(long long n) {
  if (n < 10) {
    return 1;
  }
  if (n < 100 && n % 10 != n / 10) {
    return 1;
  }
  while (n) {
    int de = fx(n % 10 - n / 10 % 10);
    if (de != 0 && (n < 100 || de + fx(n / 10 % 10 - n / 10 / 10 % 10) == 0)) {
      n /= 10;
      continue;
    } else
      return 0;
  }
  return 1;
}
vector<int> lower, higher;
int mapping[mid + 5];
int coun[1000000][10][2];
void getlower(int n, int cent) {
  if (cent < 7) {
    if (cent == 0)
      for (int i = 0; i < 10; i++) {
        getlower(n * 10 + i, cent + 1);
      }
    else {
      if (n < 10) {
        for (int i = 0; i < 10; i++)
          if (i != n) getlower(n * 10 + i, cent + 1);
      } else if (n % 10 < n / 10 % 10) {
        for (int i = n % 10 + 1; i < 10; i++) getlower(n * 10 + i, cent + 1);
      } else
        for (int i = 0; i < n % 10; i++) getlower(n * 10 + i, cent + 1);
    }
  } else
    lower.push_back(n);
}
int main() {
  long long n, k;
  cin >> n >> k;
  if (n >= mid) {
    for (long long i = n; i <= (long long)mid * mid; i += n) {
      if (isnumber(i) && !(--k)) {
        cout << i << endl;
        return 0;
      }
    }
    printf("-1\n");
  } else {
    for (int i = 1; i < mid; i++) {
      if (isnumber(i)) {
        higher.push_back(i);
        if (i % n == 0 && !(--k)) {
          cout << i << endl;
          return 0;
        }
      }
    }
    getlower(0, 0);
    int L = lower.size();
    memset(mapping, -1, sizeof(mapping));
    for (int i = 0; i < L; i++) {
      mapping[lower[i] % n] = 1;
    }
    int top = 0;
    for (int i = 0; i < n; i++) {
      if (mapping[i] != -1) {
        mapping[i] = top++;
      }
    }
    for (int i = 0; i < L; i++) {
      int x = lower[i];
      coun[mapping[x % n]][x / (mid / 10)][max(fx(x % 10 - x / 10 % 10), 0)]++;
    }
    int L2 = higher.size();
    int mo = mid % n;
    for (int i = 0; i < L2; i++) {
      int x = mapping[(n - ((long long)higher[i] * mid) % n) % n];
      if (x != -1) {
        for (int d = 0; d < 10; d++) {
          int de = fx(d - higher[i] % 10);
          if (de != 0 && (higher[i] < 10 ||
                          fx(higher[i] / 10 % 10 - higher[i] % 10) == de)) {
            int res = coun[x][d][max(de, 0)];
            if (res < k)
              k -= res;
            else {
              for (int j = 0; j < L; j++) {
                long long num = (long long)higher[i] * mid + lower[j];
                if (num % n == 0 && lower[j] / (mid / 10) == d &&
                    isnumber(num) && !(--k)) {
                  cout << num << endl;
                  return 0;
                }
              }
            }
          }
        }
      }
    }
    printf("-1\n");
  }
  return 0;
}