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>
#pragma warning(disable : 4996)
using namespace std;
long long n, m;
long long ten[20];
map<int, vector<int>> dat1;
map<int, vector<int>> dat2;
int dat3[10000000];
int dat4[100000];
bool wavy(long long x) {
  int i;
  int prev = -1, now;
  int flag = -1;
  if (x < 10000000) {
    if (dat3[x] != -1) return dat3[x];
    long long u = x;
    while (x >= 10000) {
      if (dat4[x % 10000] == 0) return dat3[u] = 0;
      x /= 100;
    }
    for (i = 0; i < 18; i++) {
      if (ten[i] > x) break;
      now = x / ten[i] % 10;
      if (prev != -1) {
        if (prev == now) return dat3[u] = 0;
        if (flag == (now > prev)) return dat3[u] = 0;
        flag = (now > prev);
      }
      prev = now;
    }
    return dat3[u] = 1;
  } else {
    for (i = 0; i < 18; i++) {
      if (ten[i] > x) break;
      now = x / ten[i] % 10;
      if (prev != -1) {
        if (prev == now) return 0;
        if (flag == (now > prev)) return 0;
        flag = (now > prev);
      }
      prev = now;
    }
    return 1;
  }
}
int wavy2(int x) {
  int i;
  int prev = -1, now;
  int flag = -1;
  if (x <= 99999)
    return 0;
  else if (x >= 1000000)
    return dat3[x] * ((x % 10 >= x / 10 % 10) + 1);
  for (i = 0; i < 7; i++) {
    now = x / ten[i] % 10;
    if (prev != -1) {
      if (prev == now) return 0;
      if (flag == (now > prev)) return 0;
      flag = (now > prev);
    }
    prev = now;
  }
  if (x % 10 < x / 10 % 10) return 1;
  return 2;
}
int main() {
  int i, j, k;
  scanf("%I64d%I64d", &n, &m);
  ten[0] = 1;
  memset(dat3, -1, sizeof(dat3));
  for (i = 0; i < 10000; i++) {
    dat4[i] |= (i / 100 % 10 < i / 10 % 10 && i % 10 < i / 10 % 10 &&
                i / 1000 > i / 100 % 10);
    dat4[i] |= (i / 100 % 10 > i / 10 % 10 && i % 10 > i / 10 % 10 &&
                i / 1000 < i / 100 % 10);
  }
  for (i = 1; i < 18; i++) ten[i] = ten[i - 1] * 10;
  if (n >= 10000000) {
    long long cnt = 0;
    for (long long now = n; now <= ten[14]; now += n) {
      if (!wavy(now)) continue;
      cnt++;
      if (cnt == m) {
        printf("%I64d", now);
        return 0;
      }
    }
    printf("-1");
    return 0;
  }
  long long now = 0;
  for (i = 1; i < 10000000; i++) {
    if (!wavy(i)) continue;
    if (i % n == 0) {
      now++;
      if (now == m) {
        printf("%d", i);
        return 0;
      }
    }
  }
  for (i = 0; i < 10000000; i++) {
    int u;
    if (!(u = wavy2(i))) continue;
    if (u == 1)
      dat1[i % n].push_back(i);
    else
      dat2[i % n].push_back(i);
  }
  int u, tu;
  for (i = 1; i < 10000000; i++) {
    if (!wavy(i)) continue;
    int mnow = (n - ((long long)i * 10000000 % n)) % n;
    if ((i < 10 || i % 10 > i / 10 % 10) && dat1.count(mnow)) {
      u = lower_bound(dat1[mnow].begin(), dat1[mnow].end(),
                      (i % 10) * 1000000) -
          dat1[mnow].begin();
      if (now + u < m) {
        now += u;
      } else {
        printf("%d%07d", i, dat1[mnow][m - now - 1]);
        return 0;
      }
    }
    if ((i < 10 || i % 10 < i / 10 % 10) && dat2.count(mnow)) {
      u = lower_bound(dat2[mnow].begin(), dat2[mnow].end(),
                      ((i % 10) + 1) * 1000000) -
          dat2[mnow].begin();
      tu = u;
      u = dat2[mnow].size() - u;
      if (now + u < m) {
        now += u;
      } else {
        printf("%d%07d", i, dat2[mnow][tu + m - now - 1]);
        return 0;
      }
    }
  }
  printf("-1");
  return 0;
}