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;
#pragma comment(linker, "/STACK:256000000")
template <class T>
T sqr(T a) {
  return a * a;
}
long long n, k;
int l = 0;
int vek[1000000];
pair<long long, int> les[1000000];
pair<long long, int> great[1000000];
int pg, pl;
int start = 22579;
void reczap(int mask, int x, int n, int q) {
  if (x == n) {
    vek[l++] = mask;
    return;
  }
  int t = mask % 10;
  mask *= 10;
  if (q) {
    for (int i = 0; i < t; ++i) reczap(mask + i, x + 1, n, 0);
  } else
    for (int i = t + 1; i < 10; ++i) reczap(mask + i, x + 1, n, 1);
}
int findls(long long pas, int c) {
  pair<long long, int> v(pas, c);
  int l = 0, r = pl, mid, ot = pl;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (les[mid] <= v)
      l = mid + 1;
    else {
      r = mid - 1;
      ot = mid;
    }
  }
  return ot;
}
int findgr(long long pas, int c) {
  pair<long long, int> v(pas, c);
  int l = 0, r = pg, mid, ot = pg;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (great[mid] <= v)
      l = mid + 1;
    else {
      r = mid - 1;
      ot = mid;
    }
  }
  return ot;
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < 10; ++i) vek[l++] = i;
  for (int i = 1; i < 7; ++i)
    for (int j = 0; j < 10; ++j) {
      if (j) reczap(j, 1, i + 1, 1);
      if (j != 9 && j) reczap(j, 1, i + 1, 0);
    }
  for (int i = 1; i < l; ++i) {
    if (!(vek[i] % n)) {
      k--;
    }
    if (!k) {
      cout << vek[i];
      return 0;
    }
    if (vek[i] > 1e5 && vek[i] < 1e6) {
      int t = (vek[i] / 10000) % 10;
      int t1 = vek[i] / 100000;
      if (t1 > t) les[pl++] = pair<int, int>(vek[i] % n, 0);
    }
    if (vek[i] > 1e6) {
      int t = (vek[i] / 100000) % 10;
      int t1 = vek[i] / 1000000;
      int q = 0;
      if (t1 > t) q = 1;
      if (q)
        great[pg++] = pair<int, int>(vek[i] % n, vek[i] / (1000000));
      else
        les[pl++] = pair<int, int>(vek[i] % n, vek[i] / (1000000));
    }
  }
  sort(great, great + pg);
  sort(les, les + pl);
  long long mod = ((long long)1e7 % n);
  for (int i = 1; i < 10; ++i) {
    long long ost = (n - (vek[i] * mod) % n) % n;
    int ind1 = findgr(ost, i);
    int ind = findgr(ost, 9);
    k -= (ind - ind1);
    if (k <= 0) {
      cout << i;
      k += ind - ind1;
      for (int j = start; j < l; ++j) {
        if (vek[j] < 1e5) continue;
        if (vek[j] < 1e6) {
          int t = (vek[j] / 10000) % 10;
          int t1 = vek[j] / 100000;
          if (t1 > t && ((vek[j] % n) == ost)) {
            k--;
            if (!k) cout << 0 << vek[j] << endl;
          }
        }
        if (vek[j] > 1e6) {
          int t = (vek[j] / 100000) % 10;
          int t1 = vek[j] / 1000000;
          if (t1 == vek[i]) continue;
          if (t1 > t && i > t1) continue;
          if (t1 < t && i < t1) continue;
          if (vek[j] % n == ost) {
            k--;
            if (!k) cout << vek[j] << endl;
          }
        }
        if (!k) {
          return 0;
        }
      }
      return 0;
    }
    ind1 = findls(ost, -1);
    ind = findls(ost, i - 1);
    k -= (ind - ind1);
    if (k <= 0) {
      cout << i;
      k += ind - ind1;
      for (int j = start; j < l; ++j) {
        if (vek[j] < 1e5) continue;
        if (vek[j] < 1e6) {
          int t = (vek[j] / 10000) % 10;
          int t1 = vek[j] / 100000;
          if (t1 > t && ((vek[j] % n) == ost)) {
            k--;
            if (!k) cout << 0 << vek[j] << endl;
          }
        }
        if (vek[j] > 1e6) {
          int t = (vek[j] / 100000) % 10;
          int t1 = vek[j] / 1000000;
          if (t1 == vek[i]) continue;
          if (t1 > t && i > t1) continue;
          if (t1 < t && i < t1) continue;
          if (vek[j] % n == ost) {
            k--;
            if (!k) cout << vek[j] << endl;
          }
        }
        if (!k) {
          return 0;
        }
      }
      return 0;
    }
  }
  for (int i = 10; i < l; ++i) {
    long long ost = (n - (vek[i] * mod) % n) % n;
    int p = vek[i] % 10;
    int p1 = (vek[i] % 100) / 10;
    int ind1, ind;
    if (p1 > p) {
      ind1 = findgr(ost, p);
      ind = findgr(ost, 9);
      k -= (ind - ind1);
    } else {
      ind1 = findls(ost, -1);
      ind = findls(ost, p - 1);
      k -= (ind - ind1);
    }
    if (k <= 0) {
      cout << vek[i];
      k += ind - ind1;
      for (int j = start; j < l; ++j) {
        if (vek[j] < 1e5) continue;
        if (vek[j] < 1e6) {
          int t = (vek[j] / 10000) % 10;
          int t1 = vek[j] / 100000;
          if (t1 > t && (vek[j] % n) == ost && p > p1) {
            k--;
            if (!k) cout << 0 << vek[j] << endl;
          }
        }
        if (vek[j] > 1e6) {
          int t = (vek[j] / 100000) % 10;
          int t1 = vek[j] / 1000000;
          if (t1 == vek[i]) continue;
          if (t1 > t && p1 > p && p < t1) {
            if (vek[j] % n == ost) {
              k--;
              if (!k) cout << vek[j] << endl;
            }
          }
          if (t1 < t && p1 < p && p > t1) {
            if (vek[j] % n == ost) {
              k--;
              if (!k) cout << vek[j] << endl;
            }
          }
        }
        if (!k) {
          return 0;
        }
      }
      return 0;
    }
  }
  cout << -1;
  return 0;
}