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>
#pragma comment(linker, "/STACK:20000000")
using namespace std;
int ri() {
  int x;
  scanf("%d", &x);
  return x;
}
long long rll() {
  long long x;
  scanf("%lld", &x);
  return x;
}
vector<int> rUP[10];
vector<int> rDOWN[10];
long long UP[10][400500];
int cntUP[10];
long long DOWN[10][400500];
int cntDOWN[10];
void solve() {
  long long n, k;
  cin >> n >> k;
  string s = "0";
  vector<int> lUP, lDOWN;
  long long temp = 0;
  int tl = 0, tr = 0;
  for (int i = (int)(1); i <= (int)(9999999); i++) {
    int pos = s.length() - 1;
    while (pos >= 0 && s[pos] == '9') pos--;
    if (pos == -1)
      s = "1" + string(s.length(), '0');
    else {
      s[pos]++;
      for (int j = (int)(pos + 1); j <= (int)(s.length() - 1); j++) s[j] = '0';
    }
    bool check = true;
    for (int j = 1; j < s.length() - 1; j++) {
      if (s[j] > s[j - 1] && s[j] > s[j + 1] ||
          s[j] < s[j - 1] && s[j] < s[j + 1])
        ;
      else
        check = false;
    }
    if (s.length() == 2 && s[0] == s[1]) check = false;
    if (check) {
      if ((long long)i % n == 0) {
        k--;
        if (k == 0) {
          cout << i << endl;
          return;
        }
      }
      if (s.length() == 1)
        lUP.push_back(i), lDOWN.push_back(i);
      else {
        if (s.length() == 7) {
          if (s[0] > s[1])
            rDOWN[s[0] - '0'].push_back(i), tl++;
          else
            rUP[s[0] - '0'].push_back(i), tr++;
        }
        if (s.length() == 6 && s[0] > s[1]) rUP[0].push_back(i), tr++;
        if (s.back() < s[s.length() - 2])
          lDOWN.push_back(i);
        else
          lUP.push_back(i);
      }
    }
  }
  cerr << tl << " " << tr << endl;
  cerr << k << endl;
  for (int i = 0; i < 10; i++) {
    UP[i][cntUP[i]++] = -1;
    UP[i][cntUP[i]++] = n + 1;
    for (int j = 0; j < rUP[i].size(); j++)
      UP[i][cntUP[i]++] = (long long)rUP[i][j] % n;
    if (i)
      for (int j = 0; j < cntUP[i - 1]; j++) UP[i][cntUP[i]++] = UP[i - 1][j];
    sort(UP[i], UP[i] + cntUP[i]);
    cerr << cntUP[i] << endl;
  }
  cerr << endl;
  for (int i = 9; i >= 0; i--) {
    DOWN[i][cntDOWN[i]++] = -1;
    DOWN[i][cntDOWN[i]++] = n + 1;
    for (int j = 0; j < rDOWN[i].size(); j++)
      DOWN[i][cntDOWN[i]++] = (long long)rDOWN[i][j] % n;
    if (i != 9)
      for (int j = 0; j < cntDOWN[i + 1]; j++)
        DOWN[i][cntDOWN[i]++] = DOWN[i + 1][j];
    sort(DOWN[i], DOWN[i] + cntDOWN[i]);
    cerr << cntDOWN[i] << endl;
  }
  for (int l = 0, r = 0; l != lUP.size() || lDOWN.size() != r;) {
    int vl = 1e9, vr = 1e9;
    if (l != lUP.size()) vl = lUP[l];
    if (r != lDOWN.size()) vr = lDOWN[r];
    if (vl <= vr) {
      l++;
      long long v = vl;
      int lastDigit = (long long)v % 10;
      if (lastDigit == 0) continue;
      lastDigit--;
      long long ost = (n - 10000000LL * (long long)v) % n;
      v *= 10000000LL;
      if (ost < 0) ost += n;
      int rpos = (int)(upper_bound(UP[lastDigit],
                                   UP[lastDigit] + cntUP[lastDigit], ost) -
                       UP[lastDigit]);
      int lpos = (int)(lower_bound(UP[lastDigit],
                                   UP[lastDigit] + cntUP[lastDigit], ost) -
                       UP[lastDigit]);
      if (rpos > lpos) {
        long long cnt = rpos - lpos;
        if (k > cnt)
          k -= cnt;
        else {
          for (int digit = 0; digit <= lastDigit; digit++)
            for (int i = 0; i < rUP[digit].size(); i++)
              if ((v + (long long)rUP[digit][i]) % n == 0) {
                k--;
                if (k == 0) {
                  cout << v / 10000000LL;
                  if (digit == 0) cout << 0;
                  cout << rUP[digit][i];
                  return;
                }
              }
        }
      }
    } else {
      r++;
      long long v = vr;
      int lastDigit = (long long)v % 10;
      if (lastDigit == 9) continue;
      lastDigit++;
      long long ost = (n - 10000000LL * (long long)v) % n;
      v *= 10000000LL;
      if (ost < 0) ost += n;
      int rpos = (int)(upper_bound(DOWN[lastDigit],
                                   DOWN[lastDigit] + cntDOWN[lastDigit], ost) -
                       DOWN[lastDigit]);
      int lpos = (int)(lower_bound(DOWN[lastDigit],
                                   DOWN[lastDigit] + cntDOWN[lastDigit], ost) -
                       DOWN[lastDigit]);
      if (rpos - lpos > 0) {
        long long cnt = rpos - lpos;
        if (k > cnt)
          k -= cnt;
        else {
          for (int digit = lastDigit; digit <= 9; digit++) {
            for (int i = 0; i < rDOWN[digit].size(); i++)
              if ((v + (long long)rDOWN[digit][i]) % n == 0) {
                k--;
                if (k == 0) {
                  cout << v / 10000000LL << rDOWN[digit][i];
                  return;
                }
              }
          }
        }
      }
    }
  }
  cout << -1 << endl;
}
int main() {
  solve();
  return 0;
}