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;
bool wave1[10000001], wave2[10000001], mark;
void *up[10], *down[10];
long long n, k;
int num[10000000];
bool isw(long long k) {
  int x, y;
  int tmp = 0;
  x = k % 10;
  k /= 10;
  while (k > 0) {
    y = k % 10;
    if (y == x) {
      return false;
    }
    if (y < x) {
      if (tmp == -1) {
        return false;
      } else {
        tmp = -1;
      }
    }
    if (y > x) {
      if (tmp == 1) {
        return false;
      } else {
        tmp = 1;
      }
    }
    k /= 10;
    x = y;
  }
  return true;
}
int main() {
  long long tmp = 0;
  long long res = 0;
  scanf("%I64d%I64d", &n, &k);
  if (n >= 10000000) {
    for (int t = 1; t < 10000000; t++) {
      long long x = n * t;
      if (x > 1e14) {
        break;
      }
      if (isw(x)) {
        res++;
      }
      if (res == k) {
        printf("%I64d\n", x);
        return 0;
      }
    }
    if (res < k) {
      printf("-1\n");
    }
    return 0;
  }
  if (n < 1e6) {
    for (int i = 0; i < 10; i++) {
      up[i] = (int *)malloc(sizeof(int) * (n + 1));
      down[i] = (int *)malloc(sizeof(int) * (n + 1));
      memset(up[i], 0, sizeof(int) * (n + 1));
      memset(down[i], 0, sizeof(int) * (n + 1));
    }
    mark = true;
  } else {
    for (int i = 0; i < 10; i++) {
      up[i] = (char *)malloc(sizeof(char) * (n + 1));
      down[i] = (char *)malloc(sizeof(char) * (n + 1));
      memset(up[i], 0, sizeof(char) * (n + 1));
      memset(down[i], 0, sizeof(char) * (n + 1));
    }
    mark = false;
  }
  for (int i = 0; i < 10000001; i++) {
    if (isw(i)) {
      wave1[i] = true;
      int x1 = i / 1000000, x2 = i / 100000 % 10, x3 = i / 10000 % 10;
      if ((x1 < x2 && x2 > x3) || (x1 > x2 && x2 < x3)) {
        wave2[i] = true;
      }
    }
  }
  long long t = 1;
  while ((tmp = t * n) < 1e7) {
    if (wave1[tmp]) {
      res++;
      if (res == k) {
        printf("%I64d\n", tmp);
        return 0;
      }
    }
    if (wave2[tmp]) {
      if (tmp / 1000000 < (tmp / 100000) % 10) {
        if (mark) {
          ((int *)up[tmp / 1000000])[0]++;
        } else {
          ((char *)up[tmp / 1000000])[0]++;
        }
      } else {
        if (mark) {
          ((int *)down[tmp / 1000000])[0]++;
        } else {
          ((char *)down[tmp / 1000000])[0]++;
        }
      }
    }
    t++;
  }
  for (; t < 10000000; t++) {
    tmp = t * n;
    int x = tmp / 10000000, y = tmp % 10000000;
    if (wave2[y]) {
      if (y / 1000000 < (y / 100000) % 10) {
        if (mark) {
          ((int *)up[y / 1000000])[x]++;
        } else {
          ((char *)up[y / 1000000])[x]++;
        }
      } else {
        if (mark) {
          ((int *)down[y / 1000000])[x]++;
        } else {
          ((char *)down[y / 1000000])[x]++;
        }
      }
      if (isw(tmp)) {
        res++;
        if (res == k) {
          printf("%I64d\n", tmp);
          return 0;
        }
      }
    }
  }
  bool flag = false;
  for (int i = n; i < 10000000; i++) {
    if (wave1[i]) {
      tmp = 0ll;
      if (i < 10) {
        for (int j = 0; j < i; j++) {
          tmp += mark ? ((int *)up[j])[i % n] : ((char *)up[j])[i % n];
        }
        for (int j = i + 1; j < 10; j++) {
          tmp += mark ? ((int *)down[j])[i % n] : ((char *)down[j])[i % n];
        }
      } else {
        if (i % 10 < (i / 10) % 10) {
          for (int j = i % 10 + 1; j < 10; j++) {
            tmp += mark ? ((int *)down[j])[i % n] : ((char *)down[j])[i % n];
          }
        } else {
          for (int j = 0; j < i % 10; j++) {
            tmp += mark ? ((int *)up[j])[i % n] : ((char *)up[j])[i % n];
          }
        }
      }
      if (res + tmp >= k) {
        tmp = i;
        flag = true;
        break;
      } else {
        res += tmp;
      }
    }
  }
  if (flag) {
    tmp *= 10000000;
    for (int i = 0; i < 10000000; i++) {
      if (wave2[i] && (tmp + i) % n == 0) {
        if (isw(tmp + i)) {
          res++;
          if (res == k) {
            printf("%I64d\n", tmp + i);
            break;
          }
        }
      }
    }
  } else {
    printf("-1\n");
  }
  return 0;
}