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 int n, k;
int dn;
long long int pn;
int cumple(long long int x, int &act) {
  if (x == 0) return -1;
  if (x < 10) return 1;
  if (x < 100) {
    if (x % 10 == x / 10 % 10) return -1;
    return 1;
  }
  int last = x % 10;
  x /= 10;
  act = x % 10;
  while (x >= 10) {
    x /= 10;
    int next = x % 10;
    if (next >= act and act >= last) return -1;
    if (next <= act and act <= last) return -1;
    last = act;
    act = next;
  }
  if (act > last) return 0;
  return 1;
}
int cuantos6 = 0;
int cuantos[1000000][10][2];
void genera(long long int c, int numd) {
  int daux;
  if (numd < dn) {
    long long int x = n - (c * pn) % n;
    if (x == n) x = 0;
    if (x < pn and 0 <= cumple(c * pn + x, daux)) {
      if (k == 1) {
        cout << c * pn + x << endl;
        exit(0);
      }
      k--;
    }
    return;
  }
  int d = c % 10;
  if (numd == 6) {
    if (c == 0) {
      if (cuantos6 < k) {
        k -= cuantos6;
        return;
      }
    } else {
      long long int x = n - (c * 1000000) % n;
      if (x == n) x = 0;
      if (c < 10) {
        int quita = 0;
        if (d < 9) quita += cuantos[x][d + 1][0];
        if (d > 0) quita += cuantos[x][d - 1][1];
        if (quita < k) {
          k -= quita;
          return;
        }
      } else {
        int dd = c % 100 / 10;
        int quita = 0;
        if (dd > d)
          quita = cuantos[x][d + 1][0];
        else
          quita = cuantos[x][d - 1][1];
        if (quita < k) {
          k -= quita;
          return;
        }
      }
    }
  }
  if (c == 0) {
    for (int dnext = 0; dnext <= 9; dnext++) genera(c * 10 + dnext, numd - 1);
  } else if (c < 10) {
    for (int dnext = 0; dnext <= 9; dnext++)
      if (dnext != d or numd == 1) genera(c * 10 + dnext, numd - 1);
  } else {
    int dd = c % 100 / 10;
    if (dd > d)
      for (int dnext = d + 1; dnext <= 9; dnext++)
        genera(c * 10 + dnext, numd - 1);
    else
      for (int dnext = 0; dnext < d; dnext++) genera(c * 10 + dnext, numd - 1);
  }
}
int main() {
  cin >> n >> k;
  if (n < 1000000) {
    {
      int d;
      for (int x = 1; x < 1000000; x++)
        cuantos6 += x % n == 0 and cumple(x, d) >= 0;
    }
    for (int x = 100000; x < 1000000; x++) {
      int d;
      int c = cumple(x, d);
      if (c >= 0) cuantos[x % n][d][c]++;
    }
    for (int x = 10000; x < 100000; x++) {
      int d;
      int c = cumple(x, d);
      if (c == 0) cuantos[x % n][0][1]++;
    }
    for (int x = 0; x < n; x++) {
      for (int d = 8; d >= 0; d--) cuantos[x][d][0] += cuantos[x][d + 1][0];
      for (int d = 1; d <= 9; d++) cuantos[x][d][1] += cuantos[x][d - 1][1];
    }
  }
  {
    long long int nn = n;
    dn = 1;
    pn = 1;
    while (nn >= 10) {
      nn /= 10;
      dn++;
      pn *= 10;
    }
  }
  genera(0, 14);
  cout << -1 << endl;
}