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;
long long N, K;
vector<long long> numbers[10][8];
long long tens[10];
int main() {
  tens[0] = 1;
  for (int i = 1; i < 10; i++) tens[i] = tens[i - 1] * 10;
  for (int i = 0; i < 10; i++) numbers[i][1].push_back(i);
  for (int i = 0; i < 100; i++)
    if (i / 10 != i % 10) numbers[i / 10][2].push_back(i);
  for (int d = 2; d <= 6; d++) {
    for (int f = 0; f < 10; f++) {
      for (long long n : numbers[f][d]) {
        long long l = n % 10;
        long long l2 = (n / 10) % 10;
        if (l2 < l) {
          for (int i = 0; i < l; i++) {
            numbers[f][d + 1].push_back(n * 10 + i);
          }
        } else if (l2 > l) {
          for (int i = l + 1; i < 10; i++) {
            numbers[f][d + 1].push_back(n * 10 + i);
          }
        }
      }
    }
  }
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 8; j++) {
      sort(numbers[i][j].begin(), numbers[i][j].end());
    }
  }
  cin >> N >> K;
  for (int n_digits = 1; n_digits <= 14; n_digits++) {
    if (n_digits < 8) {
      vector<long long> v;
      for (int i = 1; i < 10; i++) {
        for (long long n : numbers[i][n_digits]) {
          if (n % N == 0) {
            if (K == 1) {
              cout << n << endl;
              return 0;
            } else {
              K--;
            }
          }
        }
      }
    } else {
      int n_first_half = n_digits / 2;
      int n_second_half = n_digits - n_first_half;
      swap(n_first_half, n_second_half);
      map<long long, vector<long long> > M[2][10];
      for (int i = 0; i < 10; i++) {
        for (long long n : numbers[i][n_second_half]) {
          long long xx = (n / tens[n_second_half - 2]) % 10;
          if (xx > i)
            M[0][i][n % N].push_back(n);
          else if (xx < i)
            M[1][i][n % N].push_back(n);
        }
      }
      map<long long, vector<long long> > M2[2];
      for (int j = 0; j < 10; j++) {
        for (int i = 0; i < 2; i++) {
          for (auto first = M[i][j].begin(); first != M[i][j].end(); first++) {
            M2[i][first->first].resize(10, 0);
          }
        }
      }
      for (int j = 0; j < 10; j++) {
        for (int i = 0; i < 2; i++) {
          for (auto first = M[i][j].begin(); first != M[i][j].end(); first++) {
            M2[i][first->first][j] = ((int)((first->second).size()));
          }
        }
      }
      for (auto first = M2[0].begin(); first != M2[0].end(); first++) {
        for (int i = 1; i < 10; i++) {
          first->second[i] += first->second[i - 1];
        }
      }
      for (auto first = M2[1].begin(); first != M2[1].end(); first++) {
        for (int i = 8; i >= 0; i--) {
          first->second[i] += first->second[i + 1];
        }
      }
      for (int i = 1; i < 10; i++) {
        for (long long n : numbers[i][n_first_half]) {
          int l = n % 10;
          long long p = n * tens[n_second_half];
          long long m = (N - (p % N)) % N;
          int l2 = (n / 10) % 10;
          if (l2 < l) {
            if (l && M2[0].count(m)) {
              if (M2[0][m][l - 1] >= K) {
                for (int k = 0; k < l; k++) {
                  if (((int)((M[0][k][m]).size())) >= K) {
                    cout << p + M[0][k][m][K - 1] << endl;
                    return 0;
                  } else {
                    K -= ((int)((M[0][k][m]).size()));
                  }
                }
              } else {
                K -= M2[0][m][l - 1];
              }
            }
          } else if (l2 > l) {
            if (l <= 8 && M2[1].count(m)) {
              if (M2[1][m][l + 1] >= K) {
                for (int k = l + 1; k < 10; k++) {
                  if (((int)((M[1][k][m]).size())) >= K) {
                    cout << p + M[1][k][m][K - 1] << endl;
                    return 0;
                  } else {
                    K -= ((int)((M[1][k][m]).size()));
                  }
                }
              } else {
                K -= M2[1][m][l + 1];
              }
            }
          }
        }
      }
    }
  }
  printf("-1\n");
  return 0;
}