#include <bits/stdc++.h>
using namespace std;
inline void inpint(int &n) {
  n = 0;
  register int ch = getchar_unlocked();
  bool sign = 0;
  while (ch < 48 || ch > 57) {
    if (ch == '-') sign = 1;
    ch = getchar_unlocked();
  }
  while (ch >= 48 && ch <= 57) {
    n = (n << 3) + (n << 1) + ch - 48, ch = getchar_unlocked();
  }
  if (sign) n = -n;
}
inline int sqr(int x) { return x * x; }
inline int cube(int x) { return x * x * x; }
inline long long sqrLL(long long x) { return x * x; }
inline long long cubeLL(long long x) { return x * x * x; }
const long long LLINF = 9223372036854775807LL;
const long long LLINF17 = 100000000000000000LL;
const int INF = 2147483647;
const int INF9 = 1000000000;
const int MOD = 1000000007;
const double eps = 1e-7;
const double PI = acos(-1.0);
int dr[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dc[] = {0, -1, 0, 1, 1, 1, -1, -1};
long long m, k, val;
long long memo[105][105][2];
inline long long dp(int pos, int cnt, bool greater) {
  if (cnt < 0) return 0;
  if (pos == -1) {
    if (cnt == 0) return 1;
    return 0;
  }
  long long &ret = memo[pos][cnt][greater];
  if (ret != -1) return ret;
  ret = 0;
  if (greater) {
    ret += dp(pos - 1, cnt - 1, 1);
    ret += dp(pos - 1, cnt, 1);
  } else {
    for (int(i) = (0); (i) < (2); (i)++) {
      long long cur = (val >> (long long)pos) & 1LL;
      if (cur == 1) {
        if (i == 1) {
          ret += dp(pos - 1, cnt - 1, 0);
        } else if (i == 0) {
          ret += dp(pos - 1, cnt, 1);
        }
      } else if (cur == 0) {
        if (i == 0) {
          ret += dp(pos - 1, cnt, 0);
        }
      }
    }
  }
  return ret;
}
inline long long go(long long x) {
  val = x;
  memset(memo, -1, sizeof(memo));
  long long ret = dp(63, k, 0);
  return ret;
}
int main() {
  bool done = 0;
  cin >> m >> k;
  long long lo = 1, hi = 1000000000000000000LL, mid;
  while (lo <= hi) {
    mid = (lo + hi) >> 1;
    long long ret = go(2 * mid) - go(mid);
    if (ret > m)
      hi = mid - 1;
    else if (ret < m)
      lo = mid + 1;
    else {
      cout << mid << endl;
      done = 1;
      break;
    }
  }
  long long val1 = go(2 * mid) - go(mid);
  long long val2 = go(2 * lo) - go(lo);
  long long val3 = go(2 * hi) - go(hi);
  if (!done) {
    if (val1 == m)
      cout << mid << endl;
    else if (val2 == m)
      cout << lo << endl;
    else
      cout << hi << endl;
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
inline void inpint(int &n) {
  n = 0;
  register int ch = getchar_unlocked();
  bool sign = 0;
  while (ch < 48 || ch > 57) {
    if (ch == '-') sign = 1;
    ch = getchar_unlocked();
  }
  while (ch >= 48 && ch <= 57) {
    n = (n << 3) + (n << 1) + ch - 48, ch = getchar_unlocked();
  }
  if (sign) n = -n;
}
inline int sqr(int x) { return x * x; }
inline int cube(int x) { return x * x * x; }
inline long long sqrLL(long long x) { return x * x; }
inline long long cubeLL(long long x) { return x * x * x; }
const long long LLINF = 9223372036854775807LL;
const long long LLINF17 = 100000000000000000LL;
const int INF = 2147483647;
const int INF9 = 1000000000;
const int MOD = 1000000007;
const double eps = 1e-7;
const double PI = acos(-1.0);
int dr[] = {1, 0, -1, 0, -1, 1, 1, -1};
int dc[] = {0, -1, 0, 1, 1, 1, -1, -1};
long long m, k, val;
long long memo[105][105][2];
inline long long dp(int pos, int cnt, bool greater) {
  if (cnt < 0) return 0;
  if (pos == -1) {
    if (cnt == 0) return 1;
    return 0;
  }
  long long &ret = memo[pos][cnt][greater];
  if (ret != -1) return ret;
  ret = 0;
  if (greater) {
    ret += dp(pos - 1, cnt - 1, 1);
    ret += dp(pos - 1, cnt, 1);
  } else {
    for (int(i) = (0); (i) < (2); (i)++) {
      long long cur = (val >> (long long)pos) & 1LL;
      if (cur == 1) {
        if (i == 1) {
          ret += dp(pos - 1, cnt - 1, 0);
        } else if (i == 0) {
          ret += dp(pos - 1, cnt, 1);
        }
      } else if (cur == 0) {
        if (i == 0) {
          ret += dp(pos - 1, cnt, 0);
        }
      }
    }
  }
  return ret;
}
inline long long go(long long x) {
  val = x;
  memset(memo, -1, sizeof(memo));
  long long ret = dp(63, k, 0);
  return ret;
}
int main() {
  bool done = 0;
  cin >> m >> k;
  long long lo = 1, hi = 1000000000000000000LL, mid;
  while (lo <= hi) {
    mid = (lo + hi) >> 1;
    long long ret = go(2 * mid) - go(mid);
    if (ret > m)
      hi = mid - 1;
    else if (ret < m)
      lo = mid + 1;
    else {
      cout << mid << endl;
      done = 1;
      break;
    }
  }
  long long val1 = go(2 * mid) - go(mid);
  long long val2 = go(2 * lo) - go(lo);
  long long val3 = go(2 * hi) - go(hi);
  if (!done) {
    if (val1 == m)
      cout << mid << endl;
    else if (val2 == m)
      cout << lo << endl;
    else
      cout << hi << endl;
  }
  return 0;
}

```