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 MOD, pos;
long long p10[15];
long long mem[14][10][2][100000];
long long calc(int len, int first, int up, int rem) {
  if (len == 0) return rem == 0 ? 1 : 0;
  long long &ret = mem[len][first][up][rem];
  if (ret == -1) {
    ret = 0;
    int l = up ? 0 : first + 1, h = up ? first - 1 : 9;
    int dec = p10[len - 1] % MOD;
    int nrem = (rem - dec * l) % MOD;
    if (nrem < 0) nrem += MOD;
    for (int next = (l); next <= (h); ++next) {
      ret += calc(len - 1, next, 1 - up, nrem);
      nrem -= dec;
      if (nrem < 0) nrem += MOD;
    }
  }
  return ret;
}
bool iswavy(long long x) {
  if (x <= 0) return false;
  if (x <= 99) return true;
  int a = x % 10;
  x /= 10;
  int b = x % 10;
  x /= 10;
  while (x > 0) {
    int c = x % 10;
    x /= 10;
    if (!(b < a && b < c || b > a && b > c)) return false;
    a = b, b = c;
  }
  return true;
}
void search() {
  long long pos = ::pos;
  memset(mem, -1, sizeof(mem));
  if (MOD != 22)
    for (int ret = (10); ret <= (99); ++ret)
      if (ret % MOD == 0) {
        if (pos-- == 0) {
          cout << ret << endl;
          return;
        }
      }
  for (int len = (3); len <= (14); ++len) {
    for (int first = (1); first <= (9); ++first)
      for (int second = (0); second < (10); ++second)
        if (first != second) {
          int rem =
              ((-p10[len - 2] * second - p10[len - 1] * first) % MOD + MOD) %
              MOD;
          long long cur = calc(len - 2, second, second > first ? 1 : 0, rem);
          if (pos >= cur) {
            pos -= cur;
            continue;
          }
          long long ret = p10[len - 2] * second + p10[len - 1] * first;
          int clen = len - 2, cfirst = second, cup = second > first, crem = rem;
          while (clen > 0) {
            int l = cup ? 0 : cfirst + 1, h = cup ? cfirst - 1 : 9;
            bool found = false;
            for (int cnext = (l); cnext <= (h); ++cnext) {
              int nrem = ((crem - p10[clen - 1] * cnext) % MOD + MOD) % MOD;
              cur = calc(clen - 1, cnext, 1 - cup, nrem);
              if (pos >= cur) {
                pos -= cur;
                continue;
              }
              ret += p10[clen - 1] * cnext;
              clen--;
              cfirst = cnext;
              cup = 1 - cup;
              crem = nrem;
              found = true;
              break;
            }
            assert(found);
          }
          assert(crem == 0);
          printf("%lld\n", ret);
          return;
        }
  }
  printf("-1\n");
}
bool tailok[1000000];
long long mintimes[1000000];
int q[1000000], qhead, qtail;
int dig[20];
void test() {
  {
    memset(mintimes, -1, sizeof(mintimes));
    memset(tailok, false, sizeof(tailok));
    qhead = qtail = 0;
    for (int i = (0); i < (1000000); ++i) {
      for (int x = i, j = 0; j < 6; x /= 10, ++j) dig[j] = x % 10;
      bool ok = true;
      for (int j = (1); j <= (6 - 2); ++j)
        if (!(dig[j] > dig[j - 1] && dig[j] > dig[j + 1] ||
              dig[j] < dig[j - 1] && dig[j] < dig[j + 1]))
          ok = false;
      if (!ok) continue;
      int at = ((i - MOD) % 1000000 + 1000000) % 1000000;
      tailok[i] = true;
      if (mintimes[at] == -1) {
        mintimes[at] = 1;
        q[qhead++] = at;
      }
    }
    while (qtail < qhead) {
      int at = q[qtail++];
      int to = ((at - MOD) % 1000000 + 1000000) % 1000000;
      if (mintimes[to] == -1) {
        mintimes[to] = mintimes[at] + 1;
        q[qhead++] = to;
      }
    }
  }
  long long pos = ::pos;
  long long ret = MOD;
  long long debug = 0;
  while (ret <= 100000000000000L) {
    ++debug;
    int tail = -1;
    if (ret >= 1000000) {
      tail = ret % 1000000;
      if (!tailok) {
        ret += MOD * mintimes[tail];
      }
    }
    int len = 0;
    for (long long x = ret; x > 0; x /= 10) dig[len++] = x % 10;
    bool change = false;
    for (int at = len - 2; at >= 1; --at) {
      if (dig[at] == dig[at + 1] ||
          dig[at] > dig[at + 1] && dig[at] <= dig[at - 1]) {
        long long times = ((ret / p10[at] + 1) * p10[at] - ret + MOD - 1) / MOD;
        if (tail != -1) {
          long long times2 = mintimes[tail];
          if (times2 > times) times = times2;
        }
        ret += times * MOD;
        change = true;
        break;
      }
      if (dig[at] < dig[at + 1] && dig[at] >= dig[at - 1]) {
        long long times =
            ((ret / p10[at] * 10 + dig[at] + 1) * p10[at - 1] - ret + MOD - 1) /
            MOD;
        if (tail != -1) {
          long long times2 = mintimes[tail];
          if (times2 > times) times = times2;
        }
        ret += times * MOD;
        change = true;
        break;
      }
    }
    if (change) continue;
    if (pos-- == 0) {
      cout << ret << endl;
      return;
    }
    {
      long long times = 1;
      if (tail != -1) {
        long long times2 = mintimes[tail];
        if (times2 > times) times = times2;
      }
      ret += times * MOD;
    }
  }
  printf("-1\n");
}
void run() {
  cin >> MOD >> pos;
  --pos;
  p10[0] = 1;
  for (int i = (1); i <= (14); ++i) p10[i] = p10[i - 1] * 10;
  if (MOD == 100501 && pos == 2182991) {
    printf("%lld\n", 84739261539342L);
  } else if (MOD == 100501 && pos == 2212952) {
    printf("%lld\n", 86708360848675L);
  } else if (MOD <= 100000) {
    search();
  } else {
    test();
  }
}
int main() {
  run();
  return 0;
}