#include <bits/stdc++.h>
using namespace std;
int ROW[] = {+1, -1, +0, +0};
int COL[] = {+0, +0, +1, -1};
int X[] = {+0, +0, +1, -1, -1, +1, -1, +1};
int Y[] = {-1, +1, +0, +0, +1, +1, -1, -1};
int KX[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int KY[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int basePrime[] = {1009, 1013, 1019, 1021, 1031, 1223, 1229, 1231, 1237, 1249,
                   1289, 1291, 1297, 1301, 1303, 353,  359,  367,  373,  379,
                   859,  863,  877,  881,  883,  1931, 1933, 1949, 1951, 1973,
                   401,  409,  419,  421,  431,  1709, 1721, 1723, 1733, 1741,
                   3499, 3511, 3517, 3527, 3529, 929,  937,  941,  947,  953};
template <class XXX>
XXX GCD(XXX a, XXX b) {
  return b == 0 ? a : GCD(b, a % b);
}
template <class XXX>
XXX LCM(XXX a, XXX b) {
  return a * (b / GCD(a, b));
}
bool CMP(long long int a, long long int b) { return a > b; }
template <class XXX>
void fastread(XXX &number) {
  bool negative = false;
  register XXX c;
  number = 0;
  c = getchar();
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  for (; (c > 47 && c < 58); c = getchar()) number = number * 10 + c - 48;
  if (negative) number *= -1;
}
template <class XXX>
inline XXX moduler(XXX num, XXX mod) {
  return (num >= mod ? num -= mod : num);
}
inline int Set(int pos, int N) { return N = N | (1 << pos); }
inline int Reset(int pos, int N) { return N = N & ~(1 << pos); }
inline bool Check(int pos, int N) { return (bool)(N & (1 << pos)); }
void OPFILE() {}
string dec_base(unsigned long long int n, int base) {
  string res;
  while (n) {
    int r = n % base;
    if (r < 10)
      res += (r + 48);
    else
      res += (r + 55);
    n /= base;
  }
  reverse(res.begin(), res.end());
  return res;
}
string a, b;
unsigned long long int dp[70][66][3][3];
int vis[70][66][3][3], flag = 1;
unsigned long long int sol(int pos, int need, bool smaller, bool larger) {
  if (need < 0) return 0;
  if (pos >= b.size()) return (need == 0);
  unsigned long long int &ret = dp[pos][need][smaller][larger];
  if (vis[pos][need][smaller][larger] == flag) return ret;
  vis[pos][need][smaller][larger] = flag;
  ret = 0;
  for (int i = 0; i <= 1; i++) {
    if (!smaller and i > b[pos] - 48) continue;
    if (!larger and i < a[pos] - 48) continue;
    ret += sol(pos + 1, need - i, (smaller or i < b[pos] - 48),
               (larger or i > a[pos] - 48));
  }
  return ret;
}
unsigned long long int count(unsigned long long int num, int k) {
  a = dec_base(num + 1, 2);
  b = dec_base(num * 2ULL, 2);
  while (a.size() < b.size()) a = "0" + a;
  flag++;
  return sol(0, k, 0, 0);
}
int main() {
  OPFILE();
  unsigned long long int l = 1, h = 1000000000000000005;
  long long int m, k;
  cin >> m >> k;
  while (l <= h) {
    unsigned long long int mid = (l + h) / 2ULL;
    unsigned long long int cnt = count(mid, k);
    if (cnt > m)
      h = mid - 1ULL;
    else if (cnt < m)
      l = mid + 1;
    else {
      cout << mid << endl;
      break;
    }
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

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 ROW[] = {+1, -1, +0, +0};
int COL[] = {+0, +0, +1, -1};
int X[] = {+0, +0, +1, -1, -1, +1, -1, +1};
int Y[] = {-1, +1, +0, +0, +1, +1, -1, -1};
int KX[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int KY[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int basePrime[] = {1009, 1013, 1019, 1021, 1031, 1223, 1229, 1231, 1237, 1249,
                   1289, 1291, 1297, 1301, 1303, 353,  359,  367,  373,  379,
                   859,  863,  877,  881,  883,  1931, 1933, 1949, 1951, 1973,
                   401,  409,  419,  421,  431,  1709, 1721, 1723, 1733, 1741,
                   3499, 3511, 3517, 3527, 3529, 929,  937,  941,  947,  953};
template <class XXX>
XXX GCD(XXX a, XXX b) {
  return b == 0 ? a : GCD(b, a % b);
}
template <class XXX>
XXX LCM(XXX a, XXX b) {
  return a * (b / GCD(a, b));
}
bool CMP(long long int a, long long int b) { return a > b; }
template <class XXX>
void fastread(XXX &number) {
  bool negative = false;
  register XXX c;
  number = 0;
  c = getchar();
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  for (; (c > 47 && c < 58); c = getchar()) number = number * 10 + c - 48;
  if (negative) number *= -1;
}
template <class XXX>
inline XXX moduler(XXX num, XXX mod) {
  return (num >= mod ? num -= mod : num);
}
inline int Set(int pos, int N) { return N = N | (1 << pos); }
inline int Reset(int pos, int N) { return N = N & ~(1 << pos); }
inline bool Check(int pos, int N) { return (bool)(N & (1 << pos)); }
void OPFILE() {}
string dec_base(unsigned long long int n, int base) {
  string res;
  while (n) {
    int r = n % base;
    if (r < 10)
      res += (r + 48);
    else
      res += (r + 55);
    n /= base;
  }
  reverse(res.begin(), res.end());
  return res;
}
string a, b;
unsigned long long int dp[70][66][3][3];
int vis[70][66][3][3], flag = 1;
unsigned long long int sol(int pos, int need, bool smaller, bool larger) {
  if (need < 0) return 0;
  if (pos >= b.size()) return (need == 0);
  unsigned long long int &ret = dp[pos][need][smaller][larger];
  if (vis[pos][need][smaller][larger] == flag) return ret;
  vis[pos][need][smaller][larger] = flag;
  ret = 0;
  for (int i = 0; i <= 1; i++) {
    if (!smaller and i > b[pos] - 48) continue;
    if (!larger and i < a[pos] - 48) continue;
    ret += sol(pos + 1, need - i, (smaller or i < b[pos] - 48),
               (larger or i > a[pos] - 48));
  }
  return ret;
}
unsigned long long int count(unsigned long long int num, int k) {
  a = dec_base(num + 1, 2);
  b = dec_base(num * 2ULL, 2);
  while (a.size() < b.size()) a = "0" + a;
  flag++;
  return sol(0, k, 0, 0);
}
int main() {
  OPFILE();
  unsigned long long int l = 1, h = 1000000000000000005;
  long long int m, k;
  cin >> m >> k;
  while (l <= h) {
    unsigned long long int mid = (l + h) / 2ULL;
    unsigned long long int cnt = count(mid, k);
    if (cnt > m)
      h = mid - 1ULL;
    else if (cnt < m)
      l = mid + 1;
    else {
      cout << mid << endl;
      break;
    }
  }
  return 0;
}

```