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 n, k;
int sum[10][2][1111111];
int fi[1111111], z[1111111], se[1111111], nz = 0;
int cut = 7;
long long power[22];
bool ok[11111111];
vector<int> st, pq;
int np = 0, p[22];
int getModulo(int x) {
  int ans = 0;
  for (int i = 1; i <= cut - 1; i++) {
    ans = (ans + x % 10 * power[i - 1] % n) % n;
    x = x / 10;
  }
  return ans;
}
bool check(long long s, int dig) {
  np = 0;
  while (s) {
    p[++np] = s % 10;
    s /= 10;
  }
  if (dig != 0) {
    if (np < dig) {
      p[++np] = 0;
    }
  }
  if (np >= 2)
    if (p[1] == p[2]) return false;
  for (int i = 2; i <= np - 1; i++) {
    if (((p[i] > p[i - 1]) && (p[i] > p[i + 1])) ||
        ((p[i] < p[i - 1]) && (p[i] < p[i + 1]))) {
    } else {
      return false;
    }
  }
  return true;
}
void tryAll() {
  long long s = n;
  while (s <= 100000000000000ll) {
    if (check(s, 0)) {
      k--;
    }
    if (k == 0) {
      cout << s << endl;
      return;
    }
    s += n;
  }
  cout << -1 << endl;
}
void Init() {
  memset(ok, false, sizeof(ok));
  power[0] = 1;
  for (int i = 1; i <= 8; i++) power[i] = power[i - 1] * 10;
  int ncount = 0;
  st.clear();
  for (int i = 0; i <= 9; i++) st.push_back(i);
  for (int i = 1; i <= cut - 1; i++) {
    pq.clear();
    while (!st.empty()) {
      int s = st.back();
      st.pop_back();
      int news;
      ok[s] = true;
      int l = 0, r = 9;
      if (i >= 2) {
        int s1 = s % power[i - 1] / power[i - 2];
        int s0 = s % power[i] / power[i - 1];
        if (s0 == s1)
          continue;
        else if (s0 < s1) {
          l = s0 + 1;
        } else if (s0 > s1) {
          r = s0 - 1;
        }
      }
      for (int j = l; j <= r; j++) {
        news = power[i] * j + s;
        pq.push_back(news);
      }
    }
    while (!pq.empty()) {
      st.push_back(pq.back());
      pq.pop_back();
    }
  }
  while (!st.empty()) {
    int s = st.back();
    st.pop_back();
    ok[s] = true;
    int s1 = s % power[cut - 1] / power[cut - 2];
    int s0 = s % power[cut] / power[cut - 1];
    nz++;
    z[nz] = s;
    fi[nz] = s0;
    if (s1 > s0)
      se[nz] = 1;
    else if (s1 < s0)
      se[nz] = 0;
    else
      nz--;
  }
}
void SecInit() {
  memset(sum, 0, sizeof(sum));
  for (int i = 1; i <= nz; i++) {
    int value = z[i];
    int mod = getModulo(value);
    sum[fi[i]][se[i]][mod]++;
  }
}
void Trace(int digit, int tp, int mod) {
  while ((mod < 1000000)) {
    int s = digit * power[cut - 1] + mod;
    bool duoc = false;
    if ((tp == 0) && (digit > (mod / power[cut - 2]))) duoc = true;
    if ((tp == 1) && (digit < (mod / power[cut - 2]))) duoc = true;
    if (check(s, 7) && (duoc)) {
      k--;
      if (k == 0) {
        for (int i = np; i >= 1; i--) cout << p[i];
        return;
      }
    }
    mod += n;
  }
}
bool Test(int i, int j, long long mod, int l, int r, int tp) {
  for (int t = l; t <= r; t++) {
    long long nmod = (mod - power[cut - 1] * t % n + n) % n;
    if (nmod >= 1000000) continue;
    if (sum[t][tp][nmod] >= k) {
      if (i) cout << i;
      cout << j;
      Trace(t, tp, nmod);
      cout << endl;
      return true;
    } else {
      k -= sum[t][tp][nmod];
    }
  }
  return false;
}
void Solve() {
  long long s = n;
  while (s <= power[cut] - 1) {
    if (check(s, 0)) k--;
    if (k == 0) {
      cout << s << endl;
      return;
    }
    s += n;
  }
  for (int i = 0; i <= power[cut - 1] - 1; i++)
    if (ok[i]) {
      for (int j = 0; j <= 9; j++)
        if (ok[i * 10 + j] && (i || j)) {
          long long mod = power[cut] * (i * 10 + j) % n;
          mod = n - mod;
          if ((i == 0) || (i % 10 < j)) {
            int l = 0, r = j - 1, tp = 1;
            if (Test(i, j, mod, l, r, tp)) return;
          }
          if ((i == 0) || (i % 10 > j)) {
            int l = j + 1, r = 9, tp = 0;
            if (Test(i, j, mod, l, r, tp)) return;
          }
        }
    }
  cout << -1 << endl;
}
int main() {
  clock_t start, finish;
  int ntest;
  ntest = 1;
  Init();
  for (int test = 1; test <= ntest; test++) {
    cin >> n >> k;
    long long temp = k;
    if (n >= 10000000)
      tryAll();
    else {
      k = temp;
      SecInit();
      start = clock();
      Solve();
    }
  }
  finish = clock();
  return 0;
}