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];
bool debug = false;
long long mem[14][10][2][101000];
long long calc(int len, int bound, int dir, int rem) {
  if (len == 0) return rem == 0 ? 1 : 0;
  long long &ret = mem[len][bound][dir][rem];
  if (ret == -1) {
    ret = 0;
    if (dir == 1) {
      if (bound + 1 <= 9) ret += calc(len, bound + 1, dir, rem);
      if (bound - 1 >= 0) {
        int nrem = ((rem - bound * p10[len - 1]) % MOD + MOD) % MOD;
        ret += calc(len - 1, bound - 1, 1 - dir, nrem);
      }
    } else {
      if (bound - 1 >= 0) ret += calc(len, bound - 1, dir, rem);
      if (bound + 1 <= 9) {
        int nrem = ((rem - bound * p10[len - 1]) % MOD + MOD) % MOD;
        ret += calc(len - 1, bound + 1, 1 - dir, nrem);
      }
    }
  }
  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 dir = (0); dir < (2); ++dir) {
        debug = len < 3 ||
                len == 3 && (first < 4 || first == 4 && (dir < 1 || dir == 1));
        int bound = first + (dir == 0 ? -1 : +1);
        if (bound < 0 || bound > 9) continue;
        int rem = ((-p10[len - 1] * first) % MOD + MOD) % MOD;
        long long cur = calc(len - 1, bound, dir, rem);
        if (pos >= cur) {
          pos -= cur;
          continue;
        }
        long long ret = p10[len - 1] * first;
        int clen = len - 1, cbound = bound, cdir = dir, crem = rem;
        while (clen > 0) {
          if (cdir == 1) {
            if (cbound - 1 >= 0) {
              int nrem = ((crem - cbound * p10[clen - 1]) % MOD + MOD) % MOD;
              cur = calc(clen - 1, cbound - 1, 1 - cdir, nrem);
              if (pos >= cur) {
                pos -= cur;
              } else {
                ret += p10[clen - 1] * cbound;
                clen--;
                cbound--;
                cdir = 1 - cdir;
                crem = nrem;
                continue;
              }
            }
            assert(cbound + 1 <= 9);
            ++cbound;
            continue;
          } else {
            if (cbound - 1 >= 0) {
              cur = calc(clen, cbound - 1, cdir, crem);
              if (pos >= cur) {
                pos -= cur;
              } else {
                --cbound;
                continue;
              }
            }
            assert(cbound + 1 <= 9);
            int nrem = ((crem - cbound * p10[clen - 1]) % MOD + MOD) % MOD;
            ret += p10[clen - 1] * cbound;
            clen--;
            cbound++;
            cdir = 1 - cdir;
            crem = nrem;
            continue;
          }
        }
        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 <= 101000) {
    search();
  } else {
    test();
  }
}
int main() {
  run();
  return 0;
}