#include <bits/stdc++.h>
using namespace std;
int pct(int x) { return __builtin_popcount(x); }
int pct(long long x) { return __builtin_popcountll(x); }
int bt(int x) { return 31 - __builtin_clz(x); }
int bt(long long x) { return 63 - __builtin_clzll(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
long long cdiv(long long a, long long b) {
  return a / b + !(a < 0 || a % b == 0);
}
int nxt_C(int x) {
  int c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
long long nxt_C(long long x) {
  long long c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
vector<int> get_bits(int mask) {
  vector<int> bb;
  while (mask) {
    int b = bt(mask);
    bb.push_back(b);
    mask ^= (1 << b);
  }
  reverse(bb.begin(), bb.end());
  return bb;
}
int get_mask(vector<int> v) {
  int mask = 0;
  for (int x : v) {
    mask ^= (1 << x);
  }
  return mask;
}
template <typename T>
void uniq(vector<T> &v) {
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
}
template <typename T>
void leftShift(vector<T> &v, long long k) {
  k %= (int)v.size();
  if (k < 0) k += (int)v.size();
  rotate(v.begin(), v.begin() + k, v.end());
}
template <typename T>
void rightShift(vector<T> &v, long long k) {
  leftShift(v, (int)v.size() - k);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
  uniform_int_distribution<long long> uid(l, r);
  return uid(rng);
}
void sc() {}
template <typename Head, typename... Tail>
void sc(Head &H, Tail &...T) {
  cin >> H;
  sc(T...);
}
string to_string(__int128 x) {
  string s = "";
  bool neg = 0;
  if (x < 0) {
    s += "-";
    neg = 1;
    x = -x;
  }
  if (!x) s += '0';
  while (x) {
    int rem = x % 10;
    s += to_string(rem);
    x /= 10;
  }
  reverse(s.begin() + neg, s.end());
  return s;
}
const int mod = 1e9 + 7;
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * 1LL * a) % mod;
    a = (a * 1LL * a) % mod;
    b >>= 1;
  }
  return ans;
}
const int B = 68;
long long dp[B][B][2];
long long f(long long n, int k) {
  memset(dp, 0, sizeof dp);
  dp[0][0][1] = 1;
  string s = "";
  long long nn = n;
  while (nn) {
    s += char('0' + (nn & 1));
    nn >>= 1;
  }
  s += '0';
  reverse(s.begin(), s.end());
  for (int i = 0; i <= (int)s.size() - 2; i++) {
    for (int j = 0; j <= k; j++) {
      for (int kk = 0; kk <= 1; kk++) {
        if (!dp[i][j][kk]) continue;
        long long val = dp[i][j][kk];
        int cb = s[i + 1] - '0';
        for (int b = 0; b <= 1; b++) {
          if (kk && b > cb) continue;
          dp[i + 1][j + b][(kk & (b == cb))] += val;
        }
      }
    }
  }
  long long ans = dp[(int)s.size() - 1][k][0];
  return ans;
}
long long f(long long l, long long r, int k) { return f(r + 1, k) - f(l, k); }
void solve() {
  long long m;
  int k;
  sc(m, k);
  long long l = 0, r = 1e18 + 1;
  while (r - l > 1) {
    long long mid = (l + r) >> 1;
    if (f(mid + 1, 2 * mid, k) >= m)
      r = mid;
    else
      l = mid;
  }
  cout << r;
}
signed main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int tt = 1; tt <= t; tt++) {
    solve();
  }
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

One day, after a difficult lecture a diligent student Sasha saw a graffitied desk in the classroom. She came closer and read: "Find such positive integer n, that among numbers n + 1, n + 2, ..., 2·n there are exactly m numbers which binary representation contains exactly k digits one".

The girl got interested in the task and she asked you to help her solve it. Sasha knows that you are afraid of large numbers, so she guaranteed that there is an answer that doesn't exceed 1018.

Input

The first line contains two space-separated integers, m and k (0 ≤ m ≤ 1018; 1 ≤ k ≤ 64).

Output

Print the required number n (1 ≤ n ≤ 1018). If there are multiple answers, print any of them.

Examples

Input

1 1


Output

1


Input

3 2


Output

5

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int pct(int x) { return __builtin_popcount(x); }
int pct(long long x) { return __builtin_popcountll(x); }
int bt(int x) { return 31 - __builtin_clz(x); }
int bt(long long x) { return 63 - __builtin_clzll(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
long long cdiv(long long a, long long b) {
  return a / b + !(a < 0 || a % b == 0);
}
int nxt_C(int x) {
  int c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
long long nxt_C(long long x) {
  long long c = x & -x, r = x + c;
  return (((r ^ x) >> 2) / c) | r;
}
vector<int> get_bits(int mask) {
  vector<int> bb;
  while (mask) {
    int b = bt(mask);
    bb.push_back(b);
    mask ^= (1 << b);
  }
  reverse(bb.begin(), bb.end());
  return bb;
}
int get_mask(vector<int> v) {
  int mask = 0;
  for (int x : v) {
    mask ^= (1 << x);
  }
  return mask;
}
template <typename T>
void uniq(vector<T> &v) {
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
}
template <typename T>
void leftShift(vector<T> &v, long long k) {
  k %= (int)v.size();
  if (k < 0) k += (int)v.size();
  rotate(v.begin(), v.begin() + k, v.end());
}
template <typename T>
void rightShift(vector<T> &v, long long k) {
  leftShift(v, (int)v.size() - k);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
  uniform_int_distribution<long long> uid(l, r);
  return uid(rng);
}
void sc() {}
template <typename Head, typename... Tail>
void sc(Head &H, Tail &...T) {
  cin >> H;
  sc(T...);
}
string to_string(__int128 x) {
  string s = "";
  bool neg = 0;
  if (x < 0) {
    s += "-";
    neg = 1;
    x = -x;
  }
  if (!x) s += '0';
  while (x) {
    int rem = x % 10;
    s += to_string(rem);
    x /= 10;
  }
  reverse(s.begin() + neg, s.end());
  return s;
}
const int mod = 1e9 + 7;
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * 1LL * a) % mod;
    a = (a * 1LL * a) % mod;
    b >>= 1;
  }
  return ans;
}
const int B = 68;
long long dp[B][B][2];
long long f(long long n, int k) {
  memset(dp, 0, sizeof dp);
  dp[0][0][1] = 1;
  string s = "";
  long long nn = n;
  while (nn) {
    s += char('0' + (nn & 1));
    nn >>= 1;
  }
  s += '0';
  reverse(s.begin(), s.end());
  for (int i = 0; i <= (int)s.size() - 2; i++) {
    for (int j = 0; j <= k; j++) {
      for (int kk = 0; kk <= 1; kk++) {
        if (!dp[i][j][kk]) continue;
        long long val = dp[i][j][kk];
        int cb = s[i + 1] - '0';
        for (int b = 0; b <= 1; b++) {
          if (kk && b > cb) continue;
          dp[i + 1][j + b][(kk & (b == cb))] += val;
        }
      }
    }
  }
  long long ans = dp[(int)s.size() - 1][k][0];
  return ans;
}
long long f(long long l, long long r, int k) { return f(r + 1, k) - f(l, k); }
void solve() {
  long long m;
  int k;
  sc(m, k);
  long long l = 0, r = 1e18 + 1;
  while (r - l > 1) {
    long long mid = (l + r) >> 1;
    if (f(mid + 1, 2 * mid, k) >= m)
      r = mid;
    else
      l = mid;
  }
  cout << r;
}
signed main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  for (int tt = 1; tt <= t; tt++) {
    solve();
  }
  return 0;
}

```