#include <bits/stdc++.h>
using namespace std;
const long long UNDEF = -1;
const long long INF = 2e9;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
template <class T>
T extgcd(T a, T b, T& x, T& y) {
  for (T u = y = 1, v = x = 0; a;) {
    T q = b / a;
    swap(x -= q * u, u);
    swap(y -= q * v, v);
    swap(b -= q * a, a);
  }
  return b;
}
template <class T>
T mod_inv(T a, T m) {
  T x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}
const long long mc = 20;
long long C[mc][mc];
void init() {
  long long n = mc, k = mc;
  long long i, j;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= min(i, k); j++) {
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
  }
}
long long starbar(long long stars, long long parts) {
  if (parts == 0) {
    return (stars == 0) ? 1 : 0;
  }
  return C[stars + parts - 1][parts - 1];
}
const long long mn = 9;
const long long md = 16;
long long pat[mn];
long long rem[md];
long long desiredlen;
bool leadzeros;
long long gt;
long long dp[md + 2][mn + 2];
long long h(long long digit, long long len) {
  if (len > desiredlen) return 0;
  if (digit == -1) {
    if (leadzeros && len == desiredlen) return 1;
    if (!leadzeros && len <= desiredlen) return 1;
    return 0;
  }
  if (dp[digit][len] != -1) return dp[digit][len];
  long long parts = len + 1;
  if (!leadzeros && digit == 0) parts = len;
  long long ans = 0;
  for (long long stars = 0; stars <= rem[digit]; stars++) {
    ans += h(digit - 1, len + stars) * starbar(stars, parts);
  }
  return dp[digit][len] = ans;
}
long long g(bool lz, long long dlen) {
  leadzeros = lz;
  desiredlen = dlen;
  memset(dp, -1, sizeof dp);
  return h(15, 0);
}
long long f() {
  long long ans = 0;
  long long all = 0;
  for (long long x = 0; x < mn; x++) {
    for (long long d = 0; d < pat[x]; d++) {
      for (long long c = 0; c < md; c++) rem[c] = gt;
      bool isz = true;
      for (long long y = 0; y < x; y++) {
        if (pat[y] != 0) isz = false;
        if (!isz) rem[pat[y]]--;
      }
      if (d != 0) isz = false;
      if (!isz) rem[d]--;
      long long dlen = mn - x - 1;
      if (0 == (all | d)) {
        long long add = g(false, dlen) - 1;
        ans += add;
      } else {
        long long add = g(true, dlen);
        ans += add;
      }
    }
    all |= pat[x];
  }
  return ans;
}
long long go(long long x) {
  x++;
  for (long long i = mn - 1; i >= 0; i--) {
    pat[i] = x & 0xf;
    x >>= 4;
  }
  return f();
}
int main() {
  init();
  memset(rem, 0, sizeof rem);
  long long n, t;
  scanf("%lld%lld", &n, &t);
  gt = t;
  long long imin = 0, imax = 1LL << (4LL * mn);
  while (imin < imax) {
    long long imid = (imin + imax) / 2;
    long long got = go(imid);
    if (got < n)
      imin = imid + 1;
    else
      imax = imid;
  }
  printf("%llx\n", imin);
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Igor likes hexadecimal notation and considers positive integer in the hexadecimal notation interesting if each digit and each letter in it appears no more than t times. For example, if t = 3, then integers 13a13322, aaa, abcdef0123456789 are interesting, but numbers aaaa, abababab and 1000000 are not interesting.

Your task is to find the k-th smallest interesting for Igor integer in the hexadecimal notation. The integer should not contain leading zeros.

Input

The first line contains the two integers k and t (1 ≤ k ≤ 2·109, 1 ≤ t ≤ 10) — the number of the required integer and the maximum number of times some integer or letter can appear in interesting integer.

It can be shown that the answer always exists for such constraints.

Output

Print in the hexadecimal notation the only integer that is the k-th smallest interesting integer for Igor.

Examples

Input

17 1


Output

12


Input

1000000 2


Output

fca2c

Note

The first 20 interesting integers if t = 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, 10, 12, 13, 14, 15. So the answer for the first example equals 12.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long UNDEF = -1;
const long long INF = 2e9;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
template <class T>
T extgcd(T a, T b, T& x, T& y) {
  for (T u = y = 1, v = x = 0; a;) {
    T q = b / a;
    swap(x -= q * u, u);
    swap(y -= q * v, v);
    swap(b -= q * a, a);
  }
  return b;
}
template <class T>
T mod_inv(T a, T m) {
  T x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}
const long long mc = 20;
long long C[mc][mc];
void init() {
  long long n = mc, k = mc;
  long long i, j;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= min(i, k); j++) {
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
  }
}
long long starbar(long long stars, long long parts) {
  if (parts == 0) {
    return (stars == 0) ? 1 : 0;
  }
  return C[stars + parts - 1][parts - 1];
}
const long long mn = 9;
const long long md = 16;
long long pat[mn];
long long rem[md];
long long desiredlen;
bool leadzeros;
long long gt;
long long dp[md + 2][mn + 2];
long long h(long long digit, long long len) {
  if (len > desiredlen) return 0;
  if (digit == -1) {
    if (leadzeros && len == desiredlen) return 1;
    if (!leadzeros && len <= desiredlen) return 1;
    return 0;
  }
  if (dp[digit][len] != -1) return dp[digit][len];
  long long parts = len + 1;
  if (!leadzeros && digit == 0) parts = len;
  long long ans = 0;
  for (long long stars = 0; stars <= rem[digit]; stars++) {
    ans += h(digit - 1, len + stars) * starbar(stars, parts);
  }
  return dp[digit][len] = ans;
}
long long g(bool lz, long long dlen) {
  leadzeros = lz;
  desiredlen = dlen;
  memset(dp, -1, sizeof dp);
  return h(15, 0);
}
long long f() {
  long long ans = 0;
  long long all = 0;
  for (long long x = 0; x < mn; x++) {
    for (long long d = 0; d < pat[x]; d++) {
      for (long long c = 0; c < md; c++) rem[c] = gt;
      bool isz = true;
      for (long long y = 0; y < x; y++) {
        if (pat[y] != 0) isz = false;
        if (!isz) rem[pat[y]]--;
      }
      if (d != 0) isz = false;
      if (!isz) rem[d]--;
      long long dlen = mn - x - 1;
      if (0 == (all | d)) {
        long long add = g(false, dlen) - 1;
        ans += add;
      } else {
        long long add = g(true, dlen);
        ans += add;
      }
    }
    all |= pat[x];
  }
  return ans;
}
long long go(long long x) {
  x++;
  for (long long i = mn - 1; i >= 0; i--) {
    pat[i] = x & 0xf;
    x >>= 4;
  }
  return f();
}
int main() {
  init();
  memset(rem, 0, sizeof rem);
  long long n, t;
  scanf("%lld%lld", &n, &t);
  gt = t;
  long long imin = 0, imax = 1LL << (4LL * mn);
  while (imin < imax) {
    long long imid = (imin + imax) / 2;
    long long got = go(imid);
    if (got < n)
      imin = imid + 1;
    else
      imax = imid;
  }
  printf("%llx\n", imin);
}

```