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 maxs = 1000050, maxss = maxs * 20, mm = 1e7, mm1 = 1e6, mm2 = 1e5;
long long n, K, ans = -1;
int num1[maxs], s1 = 0, num2[maxs], s2 = 0;
int hs = 0, he[maxss], ne[maxs], cnt[maxs];
long long st[maxs];
long long chg(int x, int y, long long z) { return (z * 10 + x) * 10 + y; }
void push(long long sta) {
  int i, st0 = sta % maxss;
  for (i = he[st0]; i; i = ne[i])
    if (st[i] == sta) {
      cnt[i]++;
      return;
    }
  ne[++hs] = he[st0], he[st0] = hs, st[hs] = sta, cnt[hs]++;
}
int query(long long sta) {
  int i, st0 = sta % maxss;
  for (i = he[st0]; i; i = ne[i])
    if (st[i] == sta) return cnt[i];
  return 0;
}
void dfs(int x, int d) {
  if (d >= 7) {
    if (x) num1[s1++] = x;
    if (x / mm1 || (x / 100000 && x / 100000 > x / 10000 % 10)) num2[s2++] = x;
    return;
  }
  int i;
  if (x < 10) {
    for (i = 0; i <= 9; i++)
      if (!x || i != x) dfs(x * 10 + i, d + 1);
  } else if (x / 10 % 10 > x % 10)
    for (i = x % 10 + 1; i <= 9; i++) dfs(x * 10 + i, d + 1);
  else if (x / 10 % 10 < x % 10)
    for (i = 0; i < x % 10; i++) dfs(x * 10 + i, d + 1);
}
int main() {
  int i, j, k, i2;
  bool z = 0;
  scanf("%I64d%I64d", &n, &K);
  dfs(0, 0);
  for (i = 0; i < s2; i++)
    push(chg(num2[i] / mm1, num2[i] / mm2 % 10, num2[i] % n));
  for (i = 0; i < s1; i++)
    if (!(num1[i] % n) && !--K) {
      ans = num1[i];
      break;
    }
  if (K) {
    for (i = 0; i < s1; i++) {
      long long rem = (n - (long long)num1[i] * mm % n) % n;
      int tt = num1[i] % 10,
          t = (!(num1[i] / 10) ? 0 : (num1[i] / 10 % 10 > tt ? 1 : -1));
      if (t > 0)
        for (j = tt + 1; j < 10; j++) {
          for (k = 0; k < j; k++) {
            int ts = query(chg(j, k, rem));
            if (K <= ts) {
              z = 1;
              break;
            }
            K -= ts;
          }
          if (z) break;
        }
      else if (t < 0)
        for (j = 0; j < tt; j++) {
          for (k = j + 1; k < 10; k++) {
            int ts = query(chg(j, k, rem));
            if (K <= ts) {
              z = 1;
              break;
            }
            K -= ts;
          }
          if (z) break;
        }
      else {
        for (j = 0; j < tt; j++) {
          for (k = j + 1; k < 10; k++) {
            int ts = query(chg(j, k, rem));
            if (K <= ts) {
              z = 1;
              break;
            }
            K -= ts;
          }
          if (z) break;
        }
        if (!z)
          for (j = tt + 1; j < 10; j++) {
            for (k = 0; k < j; k++) {
              int ts = query(chg(j, k, rem));
              if (K <= ts) {
                z = 1;
                break;
              }
              K -= ts;
            }
            if (z) break;
          }
      }
      if (z) {
        for (i2 = 0; i2 < s2; i2++)
          if (num2[i2] / mm1 == j && num2[i2] / mm2 % 10 == k &&
              num2[i2] % n == rem && !(--K)) {
            ans = (long long)num1[i] * mm + num2[i2];
            break;
          }
        break;
      }
    }
  }
  printf("%I64d\n", ans);
  return 0;
}