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 gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long triangle(long long x) { return (((long long)(x - 1)) * (x)) / 2; }
pair<long long, long long> add(pair<long long, long long> x,
                               pair<long long, long long> y) {
  return make_pair(x.first + y.first, x.second + y.second);
}
long long modInverse(long long a) {
  long long m = 998244353;
  long long y = 0, x = 1;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) {
    x += 998244353;
  }
  return x;
}
bool isweavy2(long long n) {
  long long lastdig = n % 10;
  n /= 10;
  long long curdig = n % 10;
  n /= 10;
  if (curdig == lastdig) {
    return false;
  }
  while (n > 1) {
    long long newdig = n % 10;
    n /= 10;
    if (curdig >= lastdig && curdig <= newdig) {
      return false;
    }
    if (curdig <= lastdig && curdig >= newdig) {
      return false;
    }
    lastdig = curdig;
    curdig = newdig;
  }
  return true;
}
bool isweavy(long long n) {
  long long lastdig = n % 10;
  n /= 10;
  long long curdig = n % 10;
  n /= 10;
  if (curdig == lastdig) {
    return false;
  }
  while (n > 0) {
    long long newdig = n % 10;
    n /= 10;
    if (curdig >= lastdig && curdig <= newdig) {
      return false;
    }
    if (curdig <= lastdig && curdig >= newdig) {
      return false;
    }
    lastdig = curdig;
    curdig = newdig;
  }
  return true;
}
long long nextwavey(long long i) {
  vector<int> a;
  while (i > 0) {
    a.push_back(i % 10);
    i /= 10;
  }
  bool s = false;
  int n = a.size();
  if (a[n - 1] == a[n - 2]) {
    a[n - 2]++;
    if (a[n - 2] == 10) {
      a[n - 2] = 0;
      a[n - 1]++;
      if (a[n - 1] == 10) {
        a[n - 2] = 1;
        a[n - 1] = 0;
        a.push_back(1);
      }
    }
    s = true;
  }
  for (int i = n - 1 - 1; i > 0; i -= 1) {
    if (s) {
      if (a[i] <= a[i + 1]) {
        a[i - 1] = a[i] + 1;
      } else {
        a[i - 1] = 0;
      }
    } else {
      if (a[i] <= a[i + 1] && a[i - 1] <= a[i]) {
        a[i - 1] = a[i] + 1;
        s = true;
      }
      if (a[i] >= a[i + 1] && a[i - 1] >= a[i]) {
        a[i]++;
        a[i - 1] = 0;
        s = true;
      }
    }
  }
  while (!a.empty()) {
    i *= 10;
    i += a.back();
    a.pop_back();
  }
  return i;
}
int main() {
  ios::sync_with_stdio(false);
  long long n;
  cin >> n;
  long long k;
  cin >> k;
  long long dif = 10000000;
  if (n > dif / 5) {
    long long j = 1;
    while (j * n < dif * dif) {
      if (isweavy(j * n)) {
        k--;
        if (k == 0) {
          cout << (j)*n << endl;
          return 0;
        }
      }
      j++;
    }
    cout << -1 << endl;
    return 0;
  }
  long long j = 1;
  while (j * n < dif) {
    if (isweavy(j * n)) {
      k--;
      if (k == 0) {
        cout << (j)*n << endl;
        return 0;
      }
      j++;
    } else {
      long long newj = (nextwavey(j * n) + n - 1) / n;
      j = max(newj, j + 1);
    }
  }
  vector<vector<long long> > name(n, vector<long long>(20));
  for (int i = dif / 100; i < dif; i += 1) {
    if (isweavy2(i + dif)) {
      long long sec = i / (dif / 10);
      if (sec < (i / (dif / 100)) % 10) {
        sec += 10;
      }
      name[i % n][sec]++;
    } else {
      int newi = nextwavey(i);
      if (i < newi) {
        i = newi - 1;
      }
    }
  }
  for (int i = 1; i < dif; i += 1) {
    if (!isweavy(i)) {
      int newi = nextwavey(i);
      if (i < newi) {
        i = newi - 1;
      }
      continue;
    }
    long long intrested = (n - (i * dif) % n) % n;
    long long lastk = k;
    long long a = i % 10;
    long long b = (i / 10) % 10;
    if (i < 10 || b > a) {
      for (int j = 1; j < 10; j += 1) {
        if (a < j) {
          k -= name[intrested][j];
        }
      }
    }
    if (i < 10 || b < a) {
      for (int j = 0; j < 9; j += 1) {
        if (a > j) {
          k -= name[intrested][10 + j];
        }
      }
    }
    if (k <= 0) {
      k = lastk;
      long long j = (i * dif + n - 1) / n;
      while (j * n < dif * dif) {
        if (isweavy(j * n)) {
          k--;
          if (k == 0) {
            cout << (j)*n << endl;
            return 0;
          }
          j++;
        } else {
          long long newj = (nextwavey(j * n) + n - 1) / n;
          j = max(newj, j + 1);
        }
      }
    }
  }
  cout << -1 << endl;
  return 0;
}