#include <bits/stdc++.h>
namespace algo {
using std::swap;
const long double PI = 3.141592653589793238462643383279502884L;
const long double E = 2.718281828459045235360287471352662498L;
const long double EPS = 1e-12L;
template <typename T1, typename T2>
T1 bin_pow(T1 a, T2 n) {
  T1 r{1};
  while (n > 0) {
    if (n % 2 == 1) r *= a;
    a *= a;
    n /= 2;
  }
  return r;
}
template <typename T1, typename T2>
T1 bin_pow(T1 a, T2 n, const T1& m) {
  if (m == 1) return 0;
  T1 r{1};
  while (n > 0) {
    if (n % 2 == 1) {
      r *= a;
      r %= m;
    }
    a *= a;
    a %= m;
    n /= 2;
  }
  return r;
}
template <typename T>
T gcd(const T& a, const T& b) {
  if (b == 0) return a < 0 ? -a : a;
  return gcd(b, a % b);
}
template <typename T>
T gcd(const T& a, const T& b, T& x, T& y) {
  if (b == 0) {
    x = a < 0 ? -1 : 1;
    y = 0;
    return x * a;
  }
  T d{gcd(b, a % b, y, x)};
  y -= (a / b) * x;
  return d;
}
template <typename T>
T lcm(const T& a, const T& b) {
  T r{a / gcd(a, b) * b};
  return r < 0 ? -r : r;
}
template <typename T>
T mod_add(const T& a, const T& b, const T& m) {
  if (a < m - b) return a + b;
  return a - (m - b);
}
template <typename T>
T mod_sub(const T& a, const T& b, const T& m) {
  if (a < b) return a + (m - b);
  return a - b;
}
template <typename T>
T mod_mul(T a, T b, const T& m) {
  if (b > a) swap(a, b);
  T r{0};
  while (b > 0) {
    if (b % 2 == 1) r = mod_add(r, a, m);
    a = mod_add(a, a, m);
    b /= 2;
  }
  return r;
}
template <typename T1, typename T2>
T1 mod_pow(T1 a, T2 n, const T1& m) {
  if (m == 1) return 0;
  T1 r{1};
  while (n > 0) {
    if (n % 2 == 1) r = mod_mul(r, a, m);
    a = mod_mul(a, a, m);
    n /= 2;
  }
  return r;
}
template <typename T>
T mod_inv(const T& a, const T& m) {
  T x, y;
  T d{gcd(a, m, x, y)};
  if (d != 1) return 0;
  if (x < 0) x += m;
  return x;
}
template <typename T>
T phi(T n) {
  T t = std::sqrt(n) + EPS;
  T r = n;
  for (T i = 2; i <= t; ++i) {
    if (n % i == 0) {
      r -= r / i;
      do {
        n /= i;
      } while (n % i == 0);
      t = std::sqrt(n) + EPS;
    }
  }
  if (n > 1) r -= r / n;
  return r;
}
class LinearPhi {
 public:
  LinearPhi(uint32_t n = 1 << 20) : size_{n} {
    assert(size_ > 0 && "Size should be nonzero");
    assert(size_ <= INT32_MAX && "Size should fit into an 32-bit signed int");
    uint32_t sz = (size_ + 1) / 2;
    phi_ = new int32_t[sz];
    mark_.assign(sz, false);
    phi_[0] = 1;
    if (size_ > 1) primes_.push_back(2);
    for (uint32_t i = 1; i < sz; ++i) {
      uint32_t val = i << 1 | 1;
      if (!mark_[i]) {
        phi_[i] = val - 1;
        primes_.push_back(val);
      }
      if (val < sz) {
        for (uint32_t j = 1; j < primes_.size(); ++j) {
          uint32_t t = val * primes_[j];
          if (t > size_) break;
          mark_[t >> 1] = true;
          if (val % primes_[j] == 0) {
            phi_[t >> 1] = phi_[i] * primes_[j];
            break;
          }
          phi_[t >> 1] = phi_[i] * (primes_[j] - 1);
        }
      }
    }
  }
  LinearPhi(const LinearPhi&) = delete;
  LinearPhi& operator=(const LinearPhi&) = delete;
  ~LinearPhi() {
    delete[] phi_;
    phi_ = nullptr;
  }
  const uint32_t& size() const { return size_; }
  int32_t phi(int32_t i) const {
    int32_t r = 1;
    int k = __builtin_ctz(i);
    if (k > 0) {
      i >>= k;
      r <<= k - 1;
    }
    return r * phi_[i >> 1];
  }
  int32_t operator[](int32_t i) const { return phi(i); }
  const std::vector<int32_t>& primes() const { return primes_; }

 private:
  int32_t* phi_ = nullptr;
  std::vector<bool> mark_;
  uint32_t size_;
  std::vector<int32_t> primes_;
};
class Sieve {
 public:
  Sieve(uint32_t n = 1 << 20) : size_{n} {
    assert(size_ > 0 && "Size should be nonzero");
    assert(size_ <= INT32_MAX && "Size should fit into an 32-bit signed int");
    uint32_t sz = (size_ + 1) / 2;
    prime_.assign(sz, true);
    prime_[0] = false;
    for (uint32_t i = 1; i < sz; ++i) {
      uint32_t val = i << 1 | 1;
      if (prime_[i] && val * 1ULL * val <= size_)
        for (uint32_t j = val * val; j <= size_; j += 2 * val)
          prime_[j >> 1] = false;
    }
  }
  Sieve(const Sieve&) = delete;
  Sieve& operator=(const Sieve&) = delete;
  const uint32_t& size() const { return size_; }
  bool isPrime(const int32_t& i) const {
    if (i % 2 == 0) return i == 2;
    return prime_[i >> 1];
  }
  bool operator[](const int32_t& i) const { return isPrime(i); }

 private:
  uint32_t size_;
  std::vector<bool> prime_;
};
class LinearSieve {
 public:
  LinearSieve(uint32_t n = 1 << 20) : size_{n} {
    assert(size_ > 0 && "Size should be nonzero");
    assert(size_ <= INT32_MAX && "Size should fit into an 32-bit signed int");
    uint32_t sz = (size_ + 1) / 2;
    lpf_ = new uint16_t[sz];
    std::fill(lpf_, lpf_ + sz, 0);
    lpf_[0] = 1;
    if (size_ > 1) primes_.push_back(2);
    for (uint32_t i = 1; i < sz; ++i) {
      uint32_t val = i << 1 | 1;
      if (!lpf_[i]) primes_.push_back(val);
      if (val < sz) {
        for (uint32_t j = 1; j < primes_.size(); ++j) {
          uint32_t t = val * primes_[j];
          if (t > size_) break;
          lpf_[t >> 1] = static_cast<uint16_t>(primes_[j]);
          if (lpf_[t >> 1] == (lpf_[i] ? lpf_[i] : val)) break;
        }
      }
    }
  }
  LinearSieve(const LinearSieve&) = delete;
  LinearSieve& operator=(const LinearSieve&) = delete;
  ~LinearSieve() {
    delete[] lpf_;
    lpf_ = nullptr;
  }
  const uint32_t& size() const { return size_; }
  bool isPrime(const int32_t& i) const {
    if (i % 2 == 0) return i == 2;
    return !lpf_[i >> 1];
  }
  bool operator[](const int32_t& i) const { return isPrime(i); }
  int32_t lpf(const int32_t& i) const {
    if (i % 2 == 0) return 2;
    if (!lpf_[i >> 1]) return i;
    return lpf_[i >> 1];
  }
  int32_t phi(int32_t i) const {
    int32_t r = 1;
    int k = __builtin_ctz(i);
    if (k > 0) {
      i >>= k;
      r <<= k - 1;
    }
    int32_t n, t = lpf_[i >> 1] ? lpf_[i >> 1] : i;
    while (t != 1) {
      r *= (t - 1);
      i /= t;
      n = lpf_[i >> 1] ? lpf_[i >> 1] : i;
      while (n == t) {
        r *= n;
        i /= t;
        n = lpf_[i >> 1] ? lpf_[i >> 1] : i;
      }
      t = n;
    }
    return r;
  }
  const std::vector<int32_t>& primes() const { return primes_; }

 private:
  uint16_t* lpf_ = nullptr;
  uint32_t size_;
  std::vector<int32_t> primes_;
};
}  // namespace algo
using namespace std;
using namespace algo;
namespace task {
int k, t;
int64_t a;
int64_t dp[200][16];
int64_t c[200][200];
int d[16];
int64_t calc(int n) {
  if (n == 0) {
    return 1;
  } else {
    vector<vector<int64_t>> lp(n + 1, vector<int64_t>(16));
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 16; ++j) {
        lp[i][j] += (i <= d[j]);
        for (int s = j + 1; s < 16; ++s) {
          for (int l = 1; l + i <= n && l <= d[s]; ++l) {
            lp[i + l][s] += lp[i][j] * c[i + l][l];
          }
        }
      }
    }
    int64_t r = 0;
    for (int j = 0; j < 16; ++j) {
      r += lp[n][j];
    }
    return r;
  }
}
int main() {
  c[0][0] = 1;
  for (int i = 1; i < 200; ++i) {
    c[i][0] = 1;
    for (int j = 1; j < 200; ++j) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }
  cin >> k >> t;
  a = 0;
  for (int l = 1; l < 10; ++l) {
    for (int i = 0; i < 16; ++i) {
      d[i] = t;
    }
    int64_t g;
    vector<int> ans;
    bool ok = true;
    for (int i = 0; ok && i < l; ++i) {
      ok = false;
      for (int j = (i == 0); j < 16; ++j) {
        if (d[j] > 0) {
          --d[j];
          g = calc(l - i - 1);
          a += g;
          if (a >= k) {
            ans.push_back(j);
            ok = true;
            a -= g;
            break;
          } else {
            ++d[j];
          }
        }
      }
    }
    if (a + g == k) {
      for (int i = 0; i < ans.size(); ++i) {
        cout << (ans[i] > 9 ? char('a' + (ans[i] - 10)) : char('0' + ans[i]));
      }
      return 0;
    }
  }
  cout << '\n';
  return 0;
}
}  // namespace task
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(11);
  cout.setf(ios::fixed);
  return task::main();
}

### Prompt

Construct a CPP code solution to the problem outlined:

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>
namespace algo {
using std::swap;
const long double PI = 3.141592653589793238462643383279502884L;
const long double E = 2.718281828459045235360287471352662498L;
const long double EPS = 1e-12L;
template <typename T1, typename T2>
T1 bin_pow(T1 a, T2 n) {
  T1 r{1};
  while (n > 0) {
    if (n % 2 == 1) r *= a;
    a *= a;
    n /= 2;
  }
  return r;
}
template <typename T1, typename T2>
T1 bin_pow(T1 a, T2 n, const T1& m) {
  if (m == 1) return 0;
  T1 r{1};
  while (n > 0) {
    if (n % 2 == 1) {
      r *= a;
      r %= m;
    }
    a *= a;
    a %= m;
    n /= 2;
  }
  return r;
}
template <typename T>
T gcd(const T& a, const T& b) {
  if (b == 0) return a < 0 ? -a : a;
  return gcd(b, a % b);
}
template <typename T>
T gcd(const T& a, const T& b, T& x, T& y) {
  if (b == 0) {
    x = a < 0 ? -1 : 1;
    y = 0;
    return x * a;
  }
  T d{gcd(b, a % b, y, x)};
  y -= (a / b) * x;
  return d;
}
template <typename T>
T lcm(const T& a, const T& b) {
  T r{a / gcd(a, b) * b};
  return r < 0 ? -r : r;
}
template <typename T>
T mod_add(const T& a, const T& b, const T& m) {
  if (a < m - b) return a + b;
  return a - (m - b);
}
template <typename T>
T mod_sub(const T& a, const T& b, const T& m) {
  if (a < b) return a + (m - b);
  return a - b;
}
template <typename T>
T mod_mul(T a, T b, const T& m) {
  if (b > a) swap(a, b);
  T r{0};
  while (b > 0) {
    if (b % 2 == 1) r = mod_add(r, a, m);
    a = mod_add(a, a, m);
    b /= 2;
  }
  return r;
}
template <typename T1, typename T2>
T1 mod_pow(T1 a, T2 n, const T1& m) {
  if (m == 1) return 0;
  T1 r{1};
  while (n > 0) {
    if (n % 2 == 1) r = mod_mul(r, a, m);
    a = mod_mul(a, a, m);
    n /= 2;
  }
  return r;
}
template <typename T>
T mod_inv(const T& a, const T& m) {
  T x, y;
  T d{gcd(a, m, x, y)};
  if (d != 1) return 0;
  if (x < 0) x += m;
  return x;
}
template <typename T>
T phi(T n) {
  T t = std::sqrt(n) + EPS;
  T r = n;
  for (T i = 2; i <= t; ++i) {
    if (n % i == 0) {
      r -= r / i;
      do {
        n /= i;
      } while (n % i == 0);
      t = std::sqrt(n) + EPS;
    }
  }
  if (n > 1) r -= r / n;
  return r;
}
class LinearPhi {
 public:
  LinearPhi(uint32_t n = 1 << 20) : size_{n} {
    assert(size_ > 0 && "Size should be nonzero");
    assert(size_ <= INT32_MAX && "Size should fit into an 32-bit signed int");
    uint32_t sz = (size_ + 1) / 2;
    phi_ = new int32_t[sz];
    mark_.assign(sz, false);
    phi_[0] = 1;
    if (size_ > 1) primes_.push_back(2);
    for (uint32_t i = 1; i < sz; ++i) {
      uint32_t val = i << 1 | 1;
      if (!mark_[i]) {
        phi_[i] = val - 1;
        primes_.push_back(val);
      }
      if (val < sz) {
        for (uint32_t j = 1; j < primes_.size(); ++j) {
          uint32_t t = val * primes_[j];
          if (t > size_) break;
          mark_[t >> 1] = true;
          if (val % primes_[j] == 0) {
            phi_[t >> 1] = phi_[i] * primes_[j];
            break;
          }
          phi_[t >> 1] = phi_[i] * (primes_[j] - 1);
        }
      }
    }
  }
  LinearPhi(const LinearPhi&) = delete;
  LinearPhi& operator=(const LinearPhi&) = delete;
  ~LinearPhi() {
    delete[] phi_;
    phi_ = nullptr;
  }
  const uint32_t& size() const { return size_; }
  int32_t phi(int32_t i) const {
    int32_t r = 1;
    int k = __builtin_ctz(i);
    if (k > 0) {
      i >>= k;
      r <<= k - 1;
    }
    return r * phi_[i >> 1];
  }
  int32_t operator[](int32_t i) const { return phi(i); }
  const std::vector<int32_t>& primes() const { return primes_; }

 private:
  int32_t* phi_ = nullptr;
  std::vector<bool> mark_;
  uint32_t size_;
  std::vector<int32_t> primes_;
};
class Sieve {
 public:
  Sieve(uint32_t n = 1 << 20) : size_{n} {
    assert(size_ > 0 && "Size should be nonzero");
    assert(size_ <= INT32_MAX && "Size should fit into an 32-bit signed int");
    uint32_t sz = (size_ + 1) / 2;
    prime_.assign(sz, true);
    prime_[0] = false;
    for (uint32_t i = 1; i < sz; ++i) {
      uint32_t val = i << 1 | 1;
      if (prime_[i] && val * 1ULL * val <= size_)
        for (uint32_t j = val * val; j <= size_; j += 2 * val)
          prime_[j >> 1] = false;
    }
  }
  Sieve(const Sieve&) = delete;
  Sieve& operator=(const Sieve&) = delete;
  const uint32_t& size() const { return size_; }
  bool isPrime(const int32_t& i) const {
    if (i % 2 == 0) return i == 2;
    return prime_[i >> 1];
  }
  bool operator[](const int32_t& i) const { return isPrime(i); }

 private:
  uint32_t size_;
  std::vector<bool> prime_;
};
class LinearSieve {
 public:
  LinearSieve(uint32_t n = 1 << 20) : size_{n} {
    assert(size_ > 0 && "Size should be nonzero");
    assert(size_ <= INT32_MAX && "Size should fit into an 32-bit signed int");
    uint32_t sz = (size_ + 1) / 2;
    lpf_ = new uint16_t[sz];
    std::fill(lpf_, lpf_ + sz, 0);
    lpf_[0] = 1;
    if (size_ > 1) primes_.push_back(2);
    for (uint32_t i = 1; i < sz; ++i) {
      uint32_t val = i << 1 | 1;
      if (!lpf_[i]) primes_.push_back(val);
      if (val < sz) {
        for (uint32_t j = 1; j < primes_.size(); ++j) {
          uint32_t t = val * primes_[j];
          if (t > size_) break;
          lpf_[t >> 1] = static_cast<uint16_t>(primes_[j]);
          if (lpf_[t >> 1] == (lpf_[i] ? lpf_[i] : val)) break;
        }
      }
    }
  }
  LinearSieve(const LinearSieve&) = delete;
  LinearSieve& operator=(const LinearSieve&) = delete;
  ~LinearSieve() {
    delete[] lpf_;
    lpf_ = nullptr;
  }
  const uint32_t& size() const { return size_; }
  bool isPrime(const int32_t& i) const {
    if (i % 2 == 0) return i == 2;
    return !lpf_[i >> 1];
  }
  bool operator[](const int32_t& i) const { return isPrime(i); }
  int32_t lpf(const int32_t& i) const {
    if (i % 2 == 0) return 2;
    if (!lpf_[i >> 1]) return i;
    return lpf_[i >> 1];
  }
  int32_t phi(int32_t i) const {
    int32_t r = 1;
    int k = __builtin_ctz(i);
    if (k > 0) {
      i >>= k;
      r <<= k - 1;
    }
    int32_t n, t = lpf_[i >> 1] ? lpf_[i >> 1] : i;
    while (t != 1) {
      r *= (t - 1);
      i /= t;
      n = lpf_[i >> 1] ? lpf_[i >> 1] : i;
      while (n == t) {
        r *= n;
        i /= t;
        n = lpf_[i >> 1] ? lpf_[i >> 1] : i;
      }
      t = n;
    }
    return r;
  }
  const std::vector<int32_t>& primes() const { return primes_; }

 private:
  uint16_t* lpf_ = nullptr;
  uint32_t size_;
  std::vector<int32_t> primes_;
};
}  // namespace algo
using namespace std;
using namespace algo;
namespace task {
int k, t;
int64_t a;
int64_t dp[200][16];
int64_t c[200][200];
int d[16];
int64_t calc(int n) {
  if (n == 0) {
    return 1;
  } else {
    vector<vector<int64_t>> lp(n + 1, vector<int64_t>(16));
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < 16; ++j) {
        lp[i][j] += (i <= d[j]);
        for (int s = j + 1; s < 16; ++s) {
          for (int l = 1; l + i <= n && l <= d[s]; ++l) {
            lp[i + l][s] += lp[i][j] * c[i + l][l];
          }
        }
      }
    }
    int64_t r = 0;
    for (int j = 0; j < 16; ++j) {
      r += lp[n][j];
    }
    return r;
  }
}
int main() {
  c[0][0] = 1;
  for (int i = 1; i < 200; ++i) {
    c[i][0] = 1;
    for (int j = 1; j < 200; ++j) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }
  cin >> k >> t;
  a = 0;
  for (int l = 1; l < 10; ++l) {
    for (int i = 0; i < 16; ++i) {
      d[i] = t;
    }
    int64_t g;
    vector<int> ans;
    bool ok = true;
    for (int i = 0; ok && i < l; ++i) {
      ok = false;
      for (int j = (i == 0); j < 16; ++j) {
        if (d[j] > 0) {
          --d[j];
          g = calc(l - i - 1);
          a += g;
          if (a >= k) {
            ans.push_back(j);
            ok = true;
            a -= g;
            break;
          } else {
            ++d[j];
          }
        }
      }
    }
    if (a + g == k) {
      for (int i = 0; i < ans.size(); ++i) {
        cout << (ans[i] > 9 ? char('a' + (ans[i] - 10)) : char('0' + ans[i]));
      }
      return 0;
    }
  }
  cout << '\n';
  return 0;
}
}  // namespace task
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(11);
  cout.setf(ios::fixed);
  return task::main();
}

```