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 dp[15][10][2][80010];
long long s[10][2][80010];
long long mi[15][10];
long long cal1(int n, int len) {
  int i;
  for (i = 0; i < 10; i++) {
    for (int mod = 0; mod < n; mod++) {
      int mod1 = mod - mi[len][i];
      if (mod1 < 0) mod1 += n;
      dp[len][i][0][mod] += s[i][1][mod1];
      dp[len][i][1][mod] += s[i][0][mod1];
    }
  }
  long long ret = 0;
  for (i = 1; i < 10; i++) ret += dp[len][i][0][0] + dp[len][i][1][0];
  if (len < 3) {
    int m = len == 1 ? 10 : 100;
    ret = 0;
    for (i = len == 1 ? 1 : 10; i < m; i++)
      if (i % n == 0) {
        if (i < 10 || i % 10 - i / 10) ret++;
      }
  }
  memset(s, 0, sizeof(s));
  for (i = 8; i >= 0; i--)
    for (int mod = 0; mod < n; mod++)
      s[i][0][mod] = s[i + 1][0][mod] + dp[len][i + 1][0][mod];
  for (i = 1; i < 10; i++)
    for (int mod = 0; mod < n; mod++)
      s[i][1][mod] = s[i - 1][1][mod] + dp[len][i - 1][1][mod];
  return ret;
}
long long solve1(long long n, long long k) {
  int i, j;
  for (i = 0; i < 10; i++) s[i][1][0] = s[i][0][0] = 1;
  int anslen;
  long long ss = 0;
  for (anslen = 1; anslen <= 14; anslen++) {
    long long num = cal1(n, anslen);
    if (num >= k) break;
    k -= num;
    ss += num;
  }
  if (anslen == 15) return -1;
  long long mod = 0;
  int ans[20], cnt = 0;
  for (int len = anslen; len; len--) {
    if (len == anslen) {
      for (i = 1; i < 10; i++) {
        long long num = dp[len][i][0][mod] + dp[len][i][1][mod];
        if (anslen == 1) num = dp[len][i][0][mod];
        if (num >= k) {
          mod -= mi[len][i];
          if (mod < 0) mod += n;
          ans[cnt++] = i;
          break;
        } else
          k -= num;
      }
    } else {
      if (cnt == 1) {
        for (i = 0; i < 10; i++)
          if (i - ans[0]) {
            long long num;
            if (i < ans[0])
              num = dp[len][i][1][mod];
            else
              num = dp[len][i][0][mod];
            if (num >= k) {
              mod -= mi[len][i];
              if (mod < 0) mod += n;
              ans[cnt++] = i;
              break;
            } else
              k -= num;
          }
      } else if (ans[cnt - 1] > ans[cnt - 2]) {
        for (i = 0; i < ans[cnt - 1]; i++) {
          long long num = dp[len][i][1][mod];
          if (num >= k) {
            mod -= mi[len][i];
            if (mod < 0) mod += n;
            ans[cnt++] = i;
            break;
          } else
            k -= num;
        }
      } else {
        for (i = ans[cnt - 1] + 1; i < 10; i++) {
          long long num = dp[len][i][0][mod];
          if (num >= k) {
            mod -= mi[len][i];
            if (mod < 0) mod += n;
            ans[cnt++] = i;
            break;
          } else
            k -= num;
        }
      }
    }
  }
  long long ret = 0;
  for (i = 0; i < cnt; i++) ret = ret * 10 + ans[i];
  return ret;
}
long long K;
long long hehe;
const int base = 500009;
int cnt, first[base], nxt[base], val[base];
void ins(int pos, int v) {
  pos = pos % base;
  ++cnt;
  val[cnt] = v;
  if (!first[pos])
    first[pos] = cnt;
  else {
    pos = first[pos];
    while (nxt[pos]) pos = nxt[pos];
    nxt[pos] = cnt;
  }
}
void gao(long long pos, int v, long long& n) {
  pos %= n;
  long long gaowei = v * 1000000ll;
  int ge = v % 10, shi = v / 10 % 10;
  pos = pos % base;
  pos = first[pos];
  while (pos) {
    if ((val[pos] + gaowei) % n == 0) {
      bool valid = false;
      if (v == 0)
        valid = true;
      else if (v < 10) {
        int p1 = val[pos] / 100000;
        int p2 = val[pos] % 100000 / 10000;
        int p3 = val[pos] % 10000 / 1000;
        if ((ge > p1 && p1 < p2 && p2 > p3) || (ge < p1 && p1 > p2 && p2 < p3))
          valid = true;
      } else {
        int p1 = val[pos] / 100000;
        int p2 = val[pos] % 100000 / 10000;
        int p3 = val[pos] % 10000 / 1000;
        if ((shi > ge && ge < p1 && p1 > p2 && p2 < p3) ||
            (shi < ge && ge > p1 && p1 < p2 && p2 > p3))
          valid = true;
      }
      if (valid) {
        K--;
        if (K == 0) {
          hehe = gaowei + val[pos];
          return;
        }
      }
    }
    pos = nxt[pos];
  }
}
int in;
long long N;
void dfs(int dep, int pre, int is, int v) {
  if (hehe) return;
  if (dep == 0) {
    if (in)
      ins(v % N, v);
    else
      gao(N - (v * 1000000ll) % N, v, N);
    return;
  }
  v *= 10;
  if (is == 0) {
    for (int i = 0; i < 10; i++)
      if (i - pre) {
        if (i < pre)
          dfs(dep - 1, i, 1, v + i);
        else
          dfs(dep - 1, i, 2, v + i);
      }
  } else if (is == 1) {
    for (int i = pre + 1; i < 10; i++) dfs(dep - 1, i, 2, v + i);
  } else {
    for (int i = 0; i < pre; i++) dfs(dep - 1, i, 1, v + i);
  }
}
int main() {
  long long n, k;
  cin >> n >> k;
  int i, j;
  for (mi[1][1] = 1, i = 2; i <= 14; i++) mi[i][1] = mi[i - 1][1] * 10 % n;
  for (i = 1; i <= 14; i++)
    for (j = 0; j < 10; j++) mi[i][j] = mi[i][1] * j % n;
  long long MAX = 100000000000000ll;
  if (n > MAX / k || n * k > MAX) {
    puts("-1");
    return 0;
  }
  if (99 / n >= k) {
    cout << n * k << endl;
    return 0;
  }
  if (n <= 80000)
    cout << solve1(n, k) << endl;
  else {
    N = n, K = k;
    in = 1;
    for (i = 0; i < 6; i++)
      for (j = 1; j < 10; j++) dfs(i, j, 0, j);
    in = 0;
    dfs(0, 0, 0, 0);
    for (i = 0; i < 8; i++)
      for (j = 1; j < 10; j++) dfs(i, j, 0, j);
    if (hehe)
      cout << hehe << endl;
    else
      puts("-1");
  }
}