#include <bits/stdc++.h>
std::pair<long long, long long> count(int depth, long long low);
std::pair<long long, long long> count_r(int depth, long long low, long long lc,
                                        long long hc);
std::pair<long long, long long> count(int depth, long long low) {
  if (low == 0) {
    return std::make_pair(0, 0);
  } else {
    return count_r(depth, low, 1, 0);
  }
}
std::pair<long long, long long> count_r(int depth, long long low, long long lc,
                                        long long hc) {
  if (depth == 0) {
    if (low % 2 == 0) {
      return std::make_pair(lc, hc);
    } else {
      return std::make_pair(hc, lc);
    }
  } else {
    const long long next_low = (low - 1) / 2;
    const long long next_high = low / 2;
    long long next_lc = (low % 2 == 0) ? lc : (2 * lc + hc);
    long long next_hc = (low % 2 == 0) ? (lc + 2 * hc) : hc;
    if (next_low == 0) {
      next_lc = 0;
    }
    return count_r(depth - 1, next_low, next_lc, next_hc);
  }
}
long long minimum(int depth, long long low) {
  return (depth == 0) ? low : minimum(depth - 1, ((low - 1) / 2));
}
long long special_case_count_r(long long low, long long lc, long long hc);
long long special_case_count(long long low) {
  if (low == 0) {
    return 0;
  } else
    return special_case_count_r(low, 1, 0);
}
long long special_case_count_r(long long low, long long lc, long long hc) {
  if (low == 1) {
    return lc + 2 * hc;
  } else if (low == 2) {
    return 2 * (lc + hc);
  } else {
    const long long next_low = (low - 1) / 2;
    long long next_lc = (low % 2 == 0) ? lc : (2 * lc + hc);
    long long next_hc = (low % 2 == 0) ? (lc + 2 * hc) : hc;
    assert(next_low >= 1);
    return special_case_count_r(next_low, next_lc, next_hc);
  }
}
int main(void) {
  long long n, k;
  scanf("%lld %lld", &n, &k);
  if (k == 1) {
    puts("1");
  } else if (k == 2) {
    printf("%lld\n", n);
  } else {
    n -= 2;
    k -= 2;
    int h;
    long long l = n;
    for (h = 1; ((1LL << h) - 1) < k && l != 2 && l != 1; h++, l = (l - 1) / 2)
      ;
    h--;
    k -= (1LL << h) - 1;
    fprintf(stderr, "We can trivially apply %lld operations\n", (1LL << h) - 1);
    bool special;
    if (l == 1) {
      fprintf(stderr, "Penultimate row is 1s and 2s\n");
      special = true;
    } else if (l == 2) {
      fprintf(stderr, "Penultimate row is 2s and 3s\n");
      const auto c = count(h, n);
      if (c.second >= k) {
        fprintf(stderr,
                "There are sufficient 3s not to fall into special cases\n");
        special = false;
      } else {
        fprintf(stderr,
                "We spend an additional %lld to transmute 3s to 1s and "
                "continue with the special case\n",
                c.second);
        k -= c.second;
        special = true;
      }
    }
    if (special) {
      long long start_of_range = 2;
      for (int i = 1; n != 0 && k > 1; i++) {
        const long long left = (n - 1) / 2;
        const long long right = n / 2;
        const long long c = special_case_count(left);
        fprintf(stderr,
                "At depth %d (from root node %lld), there exists %lld in the "
                "left tree\n",
                h - i, left, c);
        fprintf(stderr, "k = %lld\n", k);
        if (n == 2) {
          k--;
          start_of_range++;
          n = right;
          continue;
        }
        if (c >= k) {
          fprintf(stderr, "There exists sufficient in the left tree\n");
          n = left;
        } else {
          fprintf(stderr, "We must enter the right tree\n");
          n = right;
          k -= c;
          start_of_range += left + 1;
        }
      }
      printf("%lld\n", start_of_range + k - 1);
    } else {
      std::pair<long long, long long> multipliers;
      if (minimum(h, n) % 2 == 0) {
        fprintf(stderr,
                "In the penultimate row, the minimum is even; we should fill "
                "odd before even\n");
        const auto c = count(h, n);
        if (c.second < k) {
          fprintf(stderr,
                  "We can trivially strike off all odd and search only even\n");
          multipliers = std::make_pair(1, 0);
          k -= c.second;
        } else {
          fprintf(stderr, "We need only search odd\n");
          multipliers = std::make_pair(0, 1);
        }
      } else {
        fprintf(stderr,
                "In the penultimate row, the minimum is odd; we should fill "
                "from left to right\n");
        multipliers = std::make_pair(1, 1);
      }
      long long start_of_range = 2;
      for (int i = 1; i <= h; i++) {
        const long long left = (n - 1) / 2;
        const long long right = n / 2;
        const auto c = count(h - i, left);
        long long delta =
            c.first * multipliers.first + c.second * multipliers.second;
        fprintf(stderr,
                "At depth %d (from root node %lld), there exists %lld in the "
                "left tree\n",
                h - i, left, delta);
        fprintf(stderr, "k = %lld\n", k);
        if (delta >= k) {
          fprintf(stderr, "There exists sufficient in the left tree\n");
          n = left;
        } else {
          fprintf(stderr, "We must enter the right tree\n");
          n = right;
          k -= delta;
          start_of_range += left + 1;
        }
      }
      printf("%lld\n", start_of_range + (n - 1) / 2);
    }
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve the following problem:

It's been long after the events of the previous problems, and Karen has now moved on from student life and is looking to relocate to a new neighborhood.

<image>

The neighborhood consists of n houses in a straight line, labelled 1 to n from left to right, all an equal distance apart.

Everyone in this neighborhood loves peace and quiet. Because of this, whenever a new person moves into the neighborhood, he or she always chooses the house whose minimum distance to any occupied house is maximized. If there are multiple houses with the maximum possible minimum distance, he or she chooses the leftmost one.

Note that the first person to arrive always moves into house 1.

Karen is the k-th person to enter this neighborhood. If everyone, including herself, follows this rule, which house will she move into?

Input

The first and only line of input contains two integers, n and k (1 ≤ k ≤ n ≤ 1018), describing the number of houses in the neighborhood, and that Karen was the k-th person to move in, respectively.

Output

Output a single integer on a line by itself, the label of the house Karen will move into.

Examples

Input

6 4


Output

2


Input

39 3


Output

20

Note

In the first test case, there are 6 houses in the neighborhood, and Karen is the fourth person to move in:

  1. The first person moves into house 1. 
  2. The second person moves into house 6. 
  3. The third person moves into house 3. 
  4. The fourth person moves into house 2. 



In the second test case, there are 39 houses in the neighborhood, and Karen is the third person to move in:

  1. The first person moves into house 1. 
  2. The second person moves into house 39. 
  3. The third person moves into house 20. 

### Response

```cpp
#include <bits/stdc++.h>
std::pair<long long, long long> count(int depth, long long low);
std::pair<long long, long long> count_r(int depth, long long low, long long lc,
                                        long long hc);
std::pair<long long, long long> count(int depth, long long low) {
  if (low == 0) {
    return std::make_pair(0, 0);
  } else {
    return count_r(depth, low, 1, 0);
  }
}
std::pair<long long, long long> count_r(int depth, long long low, long long lc,
                                        long long hc) {
  if (depth == 0) {
    if (low % 2 == 0) {
      return std::make_pair(lc, hc);
    } else {
      return std::make_pair(hc, lc);
    }
  } else {
    const long long next_low = (low - 1) / 2;
    const long long next_high = low / 2;
    long long next_lc = (low % 2 == 0) ? lc : (2 * lc + hc);
    long long next_hc = (low % 2 == 0) ? (lc + 2 * hc) : hc;
    if (next_low == 0) {
      next_lc = 0;
    }
    return count_r(depth - 1, next_low, next_lc, next_hc);
  }
}
long long minimum(int depth, long long low) {
  return (depth == 0) ? low : minimum(depth - 1, ((low - 1) / 2));
}
long long special_case_count_r(long long low, long long lc, long long hc);
long long special_case_count(long long low) {
  if (low == 0) {
    return 0;
  } else
    return special_case_count_r(low, 1, 0);
}
long long special_case_count_r(long long low, long long lc, long long hc) {
  if (low == 1) {
    return lc + 2 * hc;
  } else if (low == 2) {
    return 2 * (lc + hc);
  } else {
    const long long next_low = (low - 1) / 2;
    long long next_lc = (low % 2 == 0) ? lc : (2 * lc + hc);
    long long next_hc = (low % 2 == 0) ? (lc + 2 * hc) : hc;
    assert(next_low >= 1);
    return special_case_count_r(next_low, next_lc, next_hc);
  }
}
int main(void) {
  long long n, k;
  scanf("%lld %lld", &n, &k);
  if (k == 1) {
    puts("1");
  } else if (k == 2) {
    printf("%lld\n", n);
  } else {
    n -= 2;
    k -= 2;
    int h;
    long long l = n;
    for (h = 1; ((1LL << h) - 1) < k && l != 2 && l != 1; h++, l = (l - 1) / 2)
      ;
    h--;
    k -= (1LL << h) - 1;
    fprintf(stderr, "We can trivially apply %lld operations\n", (1LL << h) - 1);
    bool special;
    if (l == 1) {
      fprintf(stderr, "Penultimate row is 1s and 2s\n");
      special = true;
    } else if (l == 2) {
      fprintf(stderr, "Penultimate row is 2s and 3s\n");
      const auto c = count(h, n);
      if (c.second >= k) {
        fprintf(stderr,
                "There are sufficient 3s not to fall into special cases\n");
        special = false;
      } else {
        fprintf(stderr,
                "We spend an additional %lld to transmute 3s to 1s and "
                "continue with the special case\n",
                c.second);
        k -= c.second;
        special = true;
      }
    }
    if (special) {
      long long start_of_range = 2;
      for (int i = 1; n != 0 && k > 1; i++) {
        const long long left = (n - 1) / 2;
        const long long right = n / 2;
        const long long c = special_case_count(left);
        fprintf(stderr,
                "At depth %d (from root node %lld), there exists %lld in the "
                "left tree\n",
                h - i, left, c);
        fprintf(stderr, "k = %lld\n", k);
        if (n == 2) {
          k--;
          start_of_range++;
          n = right;
          continue;
        }
        if (c >= k) {
          fprintf(stderr, "There exists sufficient in the left tree\n");
          n = left;
        } else {
          fprintf(stderr, "We must enter the right tree\n");
          n = right;
          k -= c;
          start_of_range += left + 1;
        }
      }
      printf("%lld\n", start_of_range + k - 1);
    } else {
      std::pair<long long, long long> multipliers;
      if (minimum(h, n) % 2 == 0) {
        fprintf(stderr,
                "In the penultimate row, the minimum is even; we should fill "
                "odd before even\n");
        const auto c = count(h, n);
        if (c.second < k) {
          fprintf(stderr,
                  "We can trivially strike off all odd and search only even\n");
          multipliers = std::make_pair(1, 0);
          k -= c.second;
        } else {
          fprintf(stderr, "We need only search odd\n");
          multipliers = std::make_pair(0, 1);
        }
      } else {
        fprintf(stderr,
                "In the penultimate row, the minimum is odd; we should fill "
                "from left to right\n");
        multipliers = std::make_pair(1, 1);
      }
      long long start_of_range = 2;
      for (int i = 1; i <= h; i++) {
        const long long left = (n - 1) / 2;
        const long long right = n / 2;
        const auto c = count(h - i, left);
        long long delta =
            c.first * multipliers.first + c.second * multipliers.second;
        fprintf(stderr,
                "At depth %d (from root node %lld), there exists %lld in the "
                "left tree\n",
                h - i, left, delta);
        fprintf(stderr, "k = %lld\n", k);
        if (delta >= k) {
          fprintf(stderr, "There exists sufficient in the left tree\n");
          n = left;
        } else {
          fprintf(stderr, "We must enter the right tree\n");
          n = right;
          k -= delta;
          start_of_range += left + 1;
        }
      }
      printf("%lld\n", start_of_range + (n - 1) / 2);
    }
  }
  return 0;
}

```