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;
int func(int N, int K);
int main(void) {
  vector<int> menor[8];
  vector<int> maior[8];
  std::vector<pair<int, int> > wave;
  for (int i = 1; i < 10; ++i) {
    maior[1].push_back(i);
    menor[1].push_back(i);
    wave.push_back(make_pair(i, 3));
  }
  for (int k = 1; k < 7; ++k) {
    for (int i = 0; i < (int)menor[k].size(); ++i) {
      for (int j = menor[k][i] % 10 + 1; j < 10; ++j) {
        maior[k + 1].push_back(menor[k][i] * 10 + j);
        wave.push_back(make_pair(menor[k][i] * 10 + j, 2));
      }
    }
    for (int i = 0; i < (int)maior[k].size(); ++i) {
      for (int j = 0; j < maior[k][i] % 10; ++j) {
        menor[k + 1].push_back(maior[k][i] * 10 + j);
        wave.push_back(make_pair(maior[k][i] * 10 + j, 1));
      }
    }
  }
  sort((wave).begin(), (wave).end());
  long long int N, K;
  cin >> N >> K;
  if (N % 100 == 0 || K > 100000000000000 / N) {
    cout << "-1" << endl;
  } else {
    map<long long int, vector<vector<int> > > modMenor;
    map<long long int, vector<vector<int> > > modMaior;
    for (int i = 0; i < (int)menor[6].size(); ++i) {
      if ((int)modMenor[menor[6][i] % N].size() == 0) {
        modMenor[menor[6][i] % N].resize(10);
      }
      modMenor[menor[6][i] % N][0].push_back(menor[6][i]);
    }
    for (int i = 0; i < (int)menor[7].size(); ++i) {
      if ((int)modMenor[menor[7][i] % N].size() == 0) {
        modMenor[menor[7][i] % N].resize(10);
      }
      modMenor[menor[7][i] % N][menor[7][i] / 1000000].push_back(menor[7][i]);
    }
    for (int i = 0; i < (int)maior[7].size(); ++i) {
      if ((int)modMaior[maior[7][i] % N].size() == 0) {
        modMaior[maior[7][i] % N].resize(10);
      }
      modMaior[maior[7][i] % N][maior[7][i] / 1000000].push_back(maior[7][i]);
    }
    for (map<long long int, vector<vector<int> > >::iterator it =
             modMenor.begin();
         it != modMenor.end(); ++it) {
      for (vector<vector<int> >::iterator jt = (*it).second.begin();
           jt != (*it).second.end(); ++jt) {
        sort(((*jt)).begin(), ((*jt)).end());
      }
    }
    for (map<long long int, vector<vector<int> > >::iterator it =
             modMaior.begin();
         it != modMaior.end(); ++it) {
      for (vector<vector<int> >::iterator jt = (*it).second.begin();
           jt != (*it).second.end(); ++jt) {
        sort(((*jt)).begin(), ((*jt)).end());
      }
    }
    long long int sai;
    long long int cont = 0;
    for (int i = 0; i < (int)wave.size(); ++i) {
      if (wave[i].first % N == 0) {
        cont++;
        sai = wave[i].first;
        if (cont == K) break;
      }
    }
    for (int i = 0; i < (int)wave.size() && cont != K; ++i) {
      long long int lWave = (long long int)wave[i].first;
      long long int mod = (N - (lWave * 10000000 % N)) % N;
      if (wave[i].second & 2) {
        if (modMenor.count(mod) == 1) {
          for (int j = 0; j < lWave % 10; ++j) {
            if (cont + (int)modMenor[mod][j].size() < K)
              cont += (int)modMenor[mod][j].size();
            else {
              sai = lWave * 10000000 + modMenor[mod][j][K - cont - 1];
              cont = K;
              break;
            }
          }
          if (cont == K) break;
        }
      }
      if (wave[i].second & 1) {
        if (modMaior.count(mod) == 1) {
          for (int j = lWave % 10 + 1; j < 10; ++j) {
            if (cont + (int)modMaior[mod][j].size() < K)
              cont += (int)modMaior[mod][j].size();
            else {
              sai = lWave * 10000000 + modMaior[mod][j][K - cont - 1];
              cont = K;
              break;
            }
          }
        }
      }
    }
    if (cont == K) {
      cout << sai << endl;
    } else {
      cout << "-1" << endl;
    }
  }
  return 0;
}