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:128000000")
long long n, k;
vector<vector<pair<int, int> > > upstream, downstream;
vector<pair<int, int> > totalup, totaldown;
vector<int> allnumbers;
vector<int> digits;
void generate_upstream(int pos, int value, vector<pair<int, int> > &a) {
  allnumbers.push_back(value);
  if (pos == 7) {
    a.push_back(pair<int, int>((int)(value % n), value));
    digits.pop_back();
    return;
  }
  if (pos & 1) {
    for (int i = digits.back() + 1; i < 10; ++i) {
      digits.push_back(i);
      generate_upstream(pos + 1, value * 10 + i, a);
    }
  } else {
    for (int i = 0; i < digits.back(); ++i) {
      digits.push_back(i);
      generate_upstream(pos + 1, value * 10 + i, a);
    }
  }
  digits.pop_back();
}
void generate_downstream(int pos, int value, vector<pair<int, int> > &a) {
  allnumbers.push_back(value);
  if (pos == 6) {
    upstream[0].push_back(pair<int, int>((int)(value % n), value));
  }
  if (pos == 7) {
    a.push_back(pair<int, int>((int)(value % n), value));
    digits.pop_back();
    return;
  }
  if (!(pos & 1)) {
    for (int i = digits.back() + 1; i < 10; ++i) {
      digits.push_back(i);
      generate_downstream(pos + 1, value * 10 + i, a);
    }
  } else {
    for (int i = 0; i < digits.back(); ++i) {
      digits.push_back(i);
      generate_downstream(pos + 1, value * 10 + i, a);
    }
  }
  digits.pop_back();
}
inline int get_total_leftmost(vector<pair<int, int> > &a, int md, int ind) {
  pair<int, int> cur(md, (ind << 26));
  int res = (int)a.size();
  int l = 0, r = res - 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (a[mid] >= cur) {
      res = mid;
      r = mid - 1;
      continue;
    } else
      l = mid + 1;
  }
  if (res == (int)a.size()) return 0;
  if (a[res].first != md) return 0;
  return (a[res].second & 67108863);
}
inline int get_total_rightmost(vector<pair<int, int> > &a, int md, int ind) {
  pair<int, int> cur(md, (ind << 26) | 67108863);
  int res = -1;
  int l = 0, r = (int)a.size() - 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (a[mid] <= cur) {
      res = mid;
      l = mid + 1;
      continue;
    } else
      r = mid - 1;
  }
  if (res == -1) return 0;
  if (a[res].first != md) return 0;
  return (a[res].second & 67108863);
}
inline int get_leftmost(vector<pair<int, int> > &a, int md) {
  int res = -1;
  int l = 0, r = (int)a.size() - 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (a[mid].first == md) {
      res = mid;
      r = mid - 1;
      continue;
    }
    if (a[mid].first > md)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return res;
}
inline int get_rightmost(vector<pair<int, int> > &a, int md) {
  int res = -1;
  int l = 0, r = (int)a.size() - 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (a[mid].first == md) {
      res = mid;
      l = mid + 1;
      continue;
    }
    if (a[mid].first > md)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return res;
}
inline int get_count(vector<pair<int, int> > &a, int md) {
  int left_ind = get_leftmost(a, md);
  if (left_ind == -1) return 0;
  int right_ind = get_rightmost(a, md);
  return right_ind - left_ind + 1;
}
inline int get_kth(vector<pair<int, int> > &a, int md, int kvalue) {
  int left_ind = get_leftmost(a, md);
  return left_ind + kvalue - 1;
}
int main() {
  cin >> n >> k;
  upstream.resize(10);
  downstream.resize(10);
  for (int i = 1; i < 10; ++i) {
    digits.push_back(i);
    generate_upstream(1, i, upstream[i]);
    digits.push_back(i);
    generate_downstream(1, i, downstream[i]);
    sort(upstream[i].begin(), upstream[i].end());
    sort(downstream[i].begin(), downstream[i].end());
  }
  sort(upstream[0].begin(), upstream[0].end());
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < (int)upstream[i].size(); ++j)
      totalup.push_back(pair<int, int>(upstream[i][j].first, (i << 26)));
    for (int j = 0; j < (int)downstream[i].size(); ++j)
      totaldown.push_back(pair<int, int>(downstream[i][j].first, (i << 26)));
  }
  sort(totalup.begin(), totalup.end());
  sort(totaldown.begin(), totaldown.end());
  for (int i = 0; i < (int)totalup.size(); ++i) {
    ++totalup[i].second;
    if (i && totalup[i].first == totalup[i - 1].first)
      totalup[i].second += (totalup[i - 1].second & 67108863);
  }
  for (int i = (int)totaldown.size() - 1; i >= 0; --i) {
    ++totaldown[i].second;
    if (i + 1 != (int)totaldown.size() &&
        totaldown[i + 1].first == totaldown[i].first)
      totaldown[i].second += (totaldown[i + 1].second & 67108863);
  }
  sort(allnumbers.begin(), allnumbers.end());
  for (int i = 0; i < (int)allnumbers.size(); ++i) {
    if (i && allnumbers[i] == allnumbers[i - 1]) continue;
    if (allnumbers[i] % n) continue;
    --k;
    if (!k) {
      cout << allnumbers[i] << endl;
      return 0;
    }
  }
  for (int i = 0; i < (int)allnumbers.size(); ++i) {
    if (i && allnumbers[i] == allnumbers[i - 1]) continue;
    int value = allnumbers[i];
    long long md64 = (n - ((long long)value * 10000000LL) % n) % n;
    if (md64 >= 10000000LL) continue;
    int md = (int)md64;
    if (value < 10) {
      for (int i = 0; i < value; ++i) {
        int cnt = get_count(upstream[i], md);
        if (cnt < k) {
          k -= cnt;
          continue;
        }
        int ind = get_kth(upstream[i], md, (int)k);
        long long res =
            (long long)value * 10000000LL + (long long)upstream[i][ind].second;
        cout << res << endl;
        return 0;
      }
      for (int i = value + 1; i < 10; ++i) {
        int cnt = get_count(downstream[i], md);
        if (cnt < k) {
          k -= cnt;
          continue;
        }
        int ind = get_kth(downstream[i], md, (int)k);
        long long res = (long long)value * 10000000LL +
                        (long long)downstream[i][ind].second;
        cout << res << endl;
        return 0;
      }
      continue;
    }
    int last_digit = value % 10;
    int prelast_digit = (value / 10) % 10;
    if (prelast_digit < last_digit) {
      int cnt = get_total_rightmost(totalup, md, last_digit - 1);
      if (cnt < k) {
        k -= cnt;
        continue;
      }
      for (int i = 0; i < last_digit; ++i) {
        int cnt = get_count(upstream[i], md);
        if (cnt < k) {
          k -= cnt;
          continue;
        }
        int ind = get_kth(upstream[i], md, (int)k);
        long long res =
            (long long)value * 10000000LL + (long long)upstream[i][ind].second;
        cout << res << endl;
        return 0;
      }
    } else {
      int cnt = get_total_leftmost(totaldown, md, last_digit + 1);
      if (cnt < k) {
        k -= cnt;
        continue;
      }
      for (int i = last_digit + 1; i < 10; ++i) {
        int cnt = get_count(downstream[i], md);
        if (cnt < k) {
          k -= cnt;
          continue;
        }
        int ind = get_kth(downstream[i], md, (int)k);
        long long res = (long long)value * 10000000LL +
                        (long long)downstream[i][ind].second;
        cout << res << endl;
        return 0;
      }
    }
  }
  cout << -1 << endl;
  return 0;
}