Balls in a Binary Tree

You are given a full binary tree of height $h$ (see the figure).

Every edge is either open or closed. Initially all left edges are open. Starting from the root, you drop $n$ balls one by one. Each ball always travels through the currently open edge; immediately after passing through it, that edge is closed and the sibling edge of the same vertex is opened. In other words, if the left edge was open, the left one is closed and the right one is opened; if the right edge was open, the right one is closed and the left one is opened.

Determine which leaf vertex the $n$-th ball reaches. The bottom vertices are numbered from $0$ to $2^h - 1$, left to right.

The first line contains two integers $n$ and $h$ ($1 \le n \le 10^8$, $0 \le h \le 30$): the number of balls dropped and the height of the binary tree, respectively.

Print a single integer: the number of the vertex the $n$-th ball reaches.

For a tree of height $2$, the balls land in vertices numbered $0, 2, 1, 3$ in order, so the 4th ball reaches vertex $3$. When $h = 0$ the tree has a single vertex (numbered $0$), so every ball lands in vertex $0$.