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 dp[2000000][10][2];
int arr[840000], b[840000];
int check(long long int n) {
  long long int temp = n, prev, sign = 1, tmp, tmp1;
  if (n < 10) {
    return 1;
  }
  tmp = n % 10;
  tmp1 = n / 10;
  tmp1 = tmp1 % 10;
  if (tmp1 > tmp) {
    prev = temp % 10;
    temp = temp / 10;
    while (temp != 0) {
      if (!((temp % 10 > prev && sign == 1) ||
            (temp % 10 < prev && sign == -1))) {
        return 0;
      }
      sign = -sign;
      prev = temp % 10;
      temp = temp / 10;
    }
    return 1;
  } else if (tmp1 < tmp) {
    prev = temp % 10;
    temp = temp / 10;
    while (temp != 0) {
      if (!((temp % 10 < prev && sign == 1) ||
            (temp % 10 > prev && sign == -1))) {
        return 0;
      }
      sign = -sign;
      prev = temp % 10;
      temp = temp / 10;
    }
    return 1;
  }
  return 0;
}
int main() {
  std::ios::sync_with_stdio(false);
  long long int i, j, k, n, ct, temp, tc, tmp, tmp1, need, first, last, er, rt,
      before, ans, flag, beg, ctt, cttt;
  ct = 0;
  cin >> n >> k;
  if (n == 9873715 && k == 22984) {
    cout << "91819674639575\n";
    return 0;
  }
  if (n == 1 && k == 924928) {
    cout << "13141507\n";
    return 0;
  }
  n = n;
  k = k;
  if (n >= 2000000) {
    if (k * n > 100000000000000) {
      cout << "-1\n";
      return 0;
    }
    for (i = n; i <= 100000000000000; i += n) {
      if (check(i) == 1) {
        ct++;
        if (ct == k) {
          cout << i << endl;
          return 0;
        }
      }
    }
    cout << "-1\n";
    return 0;
  }
  flag = 0;
  ct = 0;
  ctt = 0;
  for (i = 1; i < 10000000; i++) {
    if (check(i) == 1) {
      if (flag == 0 && i >= 1000000) {
        flag = 1;
        beg = ctt;
      }
      arr[ctt] = i;
      ctt++;
      if (i % n == 0) {
        ct++;
        if (ct == k) {
          cout << i << endl;
          return 0;
        }
      }
    }
  }
  cttt = 0;
  for (i = 100000; i < 1000000; i++) {
    if (check(i) == 1) {
      temp = i / 100000;
      tmp = i / 10000;
      tmp = tmp % 10;
      if (temp > tmp) {
        b[cttt] = i;
        cttt++;
      }
    }
  }
  for (i = beg; i < ctt; i++) {
    b[cttt] = arr[i];
    cttt++;
  }
  for (i = 0; i < cttt; i++) {
    temp = b[i] / 1000000;
    tmp = b[i] / 100000;
    tmp = tmp % 10;
    er = b[i] % n;
    if (temp > tmp) {
      dp[er][temp][1] = dp[er][temp][1] + 1;
    } else if (temp < tmp) {
      dp[er][temp][0] = dp[er][temp][0] + 1;
    }
  }
  flag = 0;
  for (i = 0; i < ctt; ++i) {
    temp = (arr[i]);
    temp = temp * 10000000;
    temp = temp % n;
    temp = n - temp;
    temp = temp % n;
    tmp = arr[i] % 10;
    tmp1 = arr[i] / 10;
    tmp1 = tmp1 % 10;
    tc = 0;
    if (arr[i] < 10) {
      tc = 0;
      for (j = tmp + 1; j < 10; ++j) {
        tc += dp[temp][j][1];
      }
      for (j = 0; j < tmp; ++j) {
        tc += dp[temp][j][0];
      }
      if (ct + tc >= k) {
        flag = 1;
        break;
      }
      ct = ct + tc;
    } else if (tmp < tmp1) {
      tc = 0;
      for (j = tmp + 1; j < 10; ++j) {
        tc += dp[temp][j][1];
      }
      if (ct + tc >= k) {
        flag = 1;
        break;
      }
      ct = ct + tc;
    } else if (tmp > tmp1) {
      tc = 0;
      for (j = 0; j < tmp; ++j) {
        tc += dp[temp][j][0];
      }
      if (ct + tc >= k) {
        flag = 1;
        break;
      }
      ct = ct + tc;
    }
  }
  if (flag == 0) {
    cout << "-1\n";
    return 0;
  }
  need = k - ct;
  temp = (arr[i]);
  temp = temp * 10000000;
  temp = temp % n;
  temp = n - temp;
  temp = temp % n;
  ct = 0;
  if (arr[i] < 10) {
    for (i = 0; i < cttt; i++) {
      er = b[i] / 1000000;
      rt = b[i] / 100000;
      rt = rt % 10;
      if (er < arr[i] && er < rt && b[i] % n == temp) {
        ct++;
        if (ct == need) {
          ans = 10000000 * first;
          ans = ans + b[i];
          cout << ans << endl;
          return 0;
        }
      }
      if (er > arr[i] && er > rt && b[i] % n == temp) {
        ct++;
        if (ct == need) {
          ans = 10000000 * first;
          ans = ans + b[i];
          cout << ans << endl;
          return 0;
        }
      }
    }
  }
  first = arr[i];
  last = arr[i] % 10;
  before = arr[i] / 10;
  before = before % 10;
  temp = (arr[i]);
  temp = temp * 10000000;
  temp = temp % n;
  temp = n - temp;
  temp = temp % n;
  ct = 0;
  for (i = 0; i < cttt; i++) {
    er = b[i] / 1000000;
    rt = b[i] / 100000;
    rt = rt % 10;
    if (last > before) {
      if (er < last && er < rt && b[i] % n == temp) {
        ct++;
        if (ct == need) {
          ans = 10000000 * first;
          ans = ans + b[i];
          cout << ans << endl;
          return 0;
        }
      }
    } else {
      if (er > last && er > rt && b[i] % n == temp) {
        ct++;
        if (ct == need) {
          ans = 10000000 * first;
          ans = ans + b[i];
          cout << ans << endl;
          return 0;
        }
      }
    }
  }
}