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 mod = 1000000007;
int main() {
  long long n, k;
  cin >> n >> k;
  std::vector<int> l(10000000, 0);
  std::vector<int> f(10000000, 0);
  std::vector<int> s(7, 0);
  s[6] = -1;
  int ss = 1;
  int cur = 6;
  for (int i = 0; i < 10000000; i++) {
    s[cur]++;
    while (s[cur] > 9) {
      s[cur] = 0;
      cur--;
      ss = max(ss, 7 - cur);
      s[cur]++;
    }
    cur = 6;
    if (i < 10) {
      l[i] = 2;
      continue;
    }
    bool flag = true;
    if (s[6] == s[5]) flag = false;
    for (int x = 8 - ss; x < 6; x++) {
      if (s[x - 1] <= s[x])
        if (s[x] <= s[x + 1]) flag = false;
      if (s[x - 1] >= s[x])
        if (s[x] >= s[x + 1]) flag = false;
    }
    if (flag) {
      if (s[6] > s[5]) l[i] = 1;
      if (s[6] < s[5]) l[i] = -1;
    }
    for (int x = 1; x < min(8 - ss, 6); x++) {
      if (s[x - 1] <= s[x])
        if (s[x] <= s[x + 1]) flag = false;
      if (s[x - 1] >= s[x])
        if (s[x] >= s[x + 1]) flag = false;
    }
    if (!flag) continue;
    if (s[1] > s[0])
      f[i] = 1;
    else
      f[i] = -1;
  }
  if (n >= 10000000) {
    long long cnt = 0;
    long long sum = 0;
    while (1) {
      sum += n;
      if (sum > 1e14) break;
      long long yo = sum / 10000000;
      long long lo = sum % (10000000);
      if (!f[lo]) continue;
      if (!l[yo]) continue;
      if ((f[lo] == l[yo]) || (l[yo] == 2)) {
        if (f[lo] == 1) {
          if (yo % 10 > lo / 1000000) cnt++;
        } else if (f[lo] == -1) {
          if (yo % 10 < lo / 1000000) cnt++;
        }
      }
      if (f[lo] == 2) cnt++;
      if (cnt == k) {
        cout << sum;
        return 0;
      }
    }
    cout << -1;
    return 0;
  }
  vector<vector<unsigned int>> num(2, vector<unsigned int>(10000000, 0));
  for (long long i = 10000000 - n; i < 10000000; i++)
    num[0][i] = ((f[i] == -1) ? 1 : 0);
  for (long long i = 9999999 - n; i >= 0; i--)
    num[0][i] = num[0][i + n] + ((f[i] == -1) ? 1 : 0);
  for (long long i = 10000000 - n; i < 10000000; i++)
    num[1][i] = ((f[i] == 1) ? 1 : 0);
  for (long long i = 9999999 - n; i >= 0; i--)
    num[1][i] = num[1][i + n] + ((f[i] == 1) ? 1 : 0);
  long long res = 0;
  long long cnt = 0;
  long long p10 = 10000000;
  while (1) {
    res += n;
    if (res >= p10) {
      break;
    }
    if (l[res]) {
      cnt++;
    }
    if (cnt == k) {
      cout << res;
      return 0;
    }
  }
  res -= p10;
  long long curl = 1;
  while (curl < p10) {
    long long reswas = res;
    long long cntwas = cnt;
    long long step = (p10 - res + n - 1) / n;
    long long last = curl % 10;
    long long step2 = (last * 1000000 - res + n - 1) / n;
    long long step3 = ((last + 1) * 1000000 - res + n - 1) / n;
    if (res >= last * 1000000) step2 = 0;
    if (res >= (last + 1) * 1000000) step3 = 0;
    long long per = res + n * step2;
    long long per2 = res + n * step3;
    if (!l[curl]) {
      curl++;
      res = (res + step * n) % p10;
      continue;
    }
    if (l[curl] == 2) {
      if (per2 < p10) cnt += num[0][per2];
      cnt += num[1][res];
      if (per < p10) cnt -= num[1][per];
    } else if (l[curl] == -1) {
      if (per2 < p10) cnt += num[0][per2];
    } else if (l[curl] == 1) {
      cnt += num[1][res];
      if (per < p10) cnt -= num[1][per];
    }
    if (cnt >= k) {
      cnt = cntwas;
      res = reswas;
      if ((f[res] == l[curl]) || (l[curl] == 2)) {
        if (f[res]) {
          if (f[res] == 1) {
            if (curl % 10 > res / 1000000) cnt++;
          } else if (f[res] == -1) {
            if (curl % 10 < res / 1000000) {
              cnt++;
            }
          }
        }
      }
      while (1) {
        if (cnt == k) {
          cout << curl * p10 + res;
          return 0;
        }
        res += n;
        if (res >= p10) {
          res -= p10;
          curl++;
        }
        if (!f[res]) continue;
        if (!l[curl]) continue;
        if ((f[res] == l[curl]) || (l[curl] == 2)) {
          if (f[res] == 1) {
            if (curl % 10 > res / 1000000) cnt++;
          } else if (f[res] == -1) {
            if (curl % 10 < res / 1000000) cnt++;
          }
        }
      }
      return 0;
    }
    curl++;
    res = (res + step * n) % p10;
  }
  cout << -1;
}