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 MOD = 1e9 + 7;
const int SIZE = 1e6 + 10;
vector<pair<int, int> > headd[10][2];
bitset<10000000> used;
int ad[10000000];
int check(int st, long long N, int ud, long long& K, long long need) {
  if (need >= 10000000) return -1;
  int ker = lower_bound((headd[st][ud]).begin(), (headd[st][ud]).end(),
                        make_pair((int)need, 0)) -
            headd[st][ud].begin();
  int ker2 = lower_bound((headd[st][ud]).begin(), (headd[st][ud]).end(),
                         make_pair((int)need + 1, 0)) -
             headd[st][ud].begin();
  if (ker2 - ker < K) {
    K -= ker2 - ker;
    return -1;
  }
  for (int i = (ker); i < (((int)(headd[st][ud]).size())); ++i) {
    K--;
    if (K == 0) return headd[st][ud][i].second;
  }
  return -1;
}
int main() {
  long long N, K;
  cin >> N >> K;
  if (N > (1e14 + 3) / K) {
    puts("-1");
    return 0;
  }
  int tmp[8] = {};
  for (int i = (1); i < (10000000); ++i) {
    tmp[0]++;
    int now = 0;
    while (tmp[now] == 10) {
      tmp[now] = 0;
      now++;
      tmp[now]++;
    }
    bool err = 0;
    for (int j = (1); j < (6); ++j) {
      if ((tmp[j] - tmp[j - 1]) * (tmp[j] - tmp[j + 1]) <= 0) {
        err = 1;
        break;
      }
    }
    if (!err) {
      headd[tmp[6]][(tmp[6] < tmp[5]) ? 1 : 0].push_back(make_pair(i % N, i));
    }
  }
  for (int i = 0; i < (10); ++i)
    for (int j = 0; j < (2); ++j)
      sort((headd[i][j]).begin(), (headd[i][j]).end());
  for (long long now = 1; now < 10000000; now++) {
    if ((now / 10) % 10 == now % 10) continue;
    int ha = ((now / 10) % 10) < (now % 10) ? 1 : -1;
    if (now < 10 || (used[now / 10] && (ad[now / 10] != ha))) {
      if (now < 10) ha = 0;
      if (now % N == 0) {
        K--;
        if (K == 0) {
          cout << now << endl;
          return 0;
        }
      }
      ad[now] = ha;
      used[now] = 1;
    }
  }
  for (int i = (1); i < (10000000); ++i) {
    if (used[i]) {
      int tail = i % 10;
      int flag = 0;
      if (i >= 10) {
        if ((i / 10) % 10 < tail)
          flag = 1;
        else
          flag = -1;
      }
      long long r = (i * 10000000LL) % N;
      long long need = N - r;
      if (need == N) need = 0;
      if (flag != -1) {
        for (int j = 0; j < (tail); ++j) {
          int res = check(j, N, 1, K, need);
          if (res >= 0) {
            printf("%d%07d\n", i, res);
            return 0;
          }
        }
      }
      if (flag != 1)
        for (int j = (tail + 1); j < (10); ++j) {
          int res = check(j, N, 0, K, need);
          if (res >= 0) {
            printf("%d%07d\n", i, res);
            return 0;
          }
        }
    }
  }
  puts("-1");
  return 0;
}