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;
struct para {
  int x, mono;
};
long long d, n;
vector<int> w;
vector<para> wp;
map<long long, vector<int> > Mr, Mm;
map<long long, vector<int> > MrK, MmK;
void rec1(int akt, int dl, int c, int mono) {
  akt = akt * 10 + c;
  if (akt % d == 0) w.push_back(akt);
  if (dl == 7) return;
  if (dl == 1) {
    for (int i = 0; i <= 9; ++i) {
      if (i < c) rec1(akt, dl + 1, i, -1);
      if (i > c) rec1(akt, dl + 1, i, 1);
    }
  } else {
    if ((mono == 1 && dl % 2 == 1) || (mono == -1 && dl % 2 == 0))
      for (int i = c + 1; i <= 9; ++i) rec1(akt, dl + 1, i, mono);
    else
      for (int i = 0; i < c; ++i) rec1(akt, dl + 1, i, mono);
  }
}
void rec2(int akt, int dl, int c, int mono, int max_dl) {
  akt = akt * 10 + c;
  if (dl == max_dl) {
    wp.push_back({akt, mono});
    return;
  }
  if (dl == 1) {
    for (int i = 0; i <= 9; ++i) {
      if (i < c) rec2(akt, dl + 1, i, -1, max_dl);
      if (i > c) rec2(akt, dl + 1, i, 1, max_dl);
    }
  } else {
    if ((mono == 1 && dl % 2 == 1) || (mono == -1 && dl % 2 == 0))
      for (int i = c + 1; i <= 9; ++i) rec2(akt, dl + 1, i, mono, max_dl);
    else
      for (int i = 0; i < c; ++i) rec2(akt, dl + 1, i, mono, max_dl);
  }
}
void rec3(int akt, int dl, int c, int mono, int max_dl,
          map<long long, vector<int> >& M1, map<long long, vector<int> >& M2) {
  akt = akt * 10 + c;
  if (dl == max_dl) {
    if (mono == 1)
      M1[akt % d].push_back(akt);
    else
      M2[akt % d].push_back(akt);
    return;
  }
  if (dl == 1) {
    for (int i = 0; i <= 9; ++i) {
      if (i < c) rec3(akt, dl + 1, i, -1, max_dl, M1, M2);
      if (i > c) rec3(akt, dl + 1, i, 1, max_dl, M1, M2);
    }
  } else {
    if ((mono == 1 && dl % 2 == 1) || (mono == -1 && dl % 2 == 0))
      for (int i = c + 1; i <= 9; ++i)
        rec3(akt, dl + 1, i, mono, max_dl, M1, M2);
    else
      for (int i = 0; i < c; ++i) rec3(akt, dl + 1, i, mono, max_dl, M1, M2);
  }
}
int Szukaj1(vector<int>& a, int x) {
  if (a.size() == 0) return -1;
  int l = 0, p = a.size() - 1, s, r = -1;
  while (l <= p) {
    s = (l + p) / 2;
    if (a[s] >= x) {
      r = s;
      p = s - 1;
    } else
      l = s + 1;
  }
  return r;
}
int Szukaj2(vector<int>& a, int x) {
  if (a.size() == 0) return -1;
  int l = 0, p = a.size() - 1, s, r = -1;
  while (l <= p) {
    s = (l + p) / 2;
    if (a[s] <= x) {
      r = s;
      l = s + 1;
    } else
      p = s - 1;
  }
  return r;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> d >> n;
  for (int i = 1; i <= 9; ++i) rec1(0, 1, i, 0);
  sort(w.begin(), w.end());
  if (n <= w.size()) {
    cout << w[n - 1];
    return 0;
  }
  n -= w.size();
  for (int i = 8; i <= 14; ++i) {
    Mr.clear();
    Mm.clear();
    MrK.clear();
    MmK.clear();
    wp.clear();
    int pref = i / 2;
    int suf = i - pref;
    for (int j = 1; j <= 9; ++j) rec2(0, 1, j, 0, pref);
    for (int j = 1; j <= 9; ++j) rec3(0, 1, j, 0, suf, Mr, Mm);
    for (int j = 1; j <= 9; ++j) rec3(0, 1, j, 0, suf - 1, MrK, MmK);
    for (int j = 0; j < wp.size(); ++j) {
      long long r_pref = wp[j].x % d;
      for (int k = 0; k < suf; ++k) r_pref = (10 * r_pref) % d;
      long long r_suf = d - r_pref;
      if (r_suf == d) r_suf = 0;
      if ((wp[j].mono == 1 && pref % 2 == 0) ||
          (wp[j].mono == -1 && pref % 2 == 1)) {
        if (n <= MmK[r_suf].size()) {
          cout << wp[j].x << "0" << MmK[r_suf][n - 1];
          return 0;
        }
        n -= MmK[r_suf].size();
      }
      if ((wp[j].mono == 1 && pref % 2 == 0) ||
          (wp[j].mono == -1 && pref % 2 == 1)) {
        int pot = wp[j].x % 10;
        for (int k = 0; k < suf - 1; ++k) pot *= 10;
        int pos = Szukaj2(Mr[r_suf], pot - 1);
        if (pos != -1) {
          if (n <= pos + 1) {
            cout << wp[j].x << Mr[r_suf][n - 1];
            return 0;
          }
          n -= pos + 1;
        }
      } else {
        int pot = wp[j].x % 10 + 1;
        for (int k = 0; k < suf - 1; ++k) pot *= 10;
        int pos = Szukaj1(Mm[r_suf], pot);
        if (pos != -1) {
          if (n <= Mm[r_suf].size() - pos) {
            cout << wp[j].x << Mm[r_suf][pos + n - 1];
            return 0;
          }
          n -= Mm[r_suf].size() - pos;
        }
      }
    }
  }
  cout << "-1";
  return 0;
}