P15837 [Lqiao Cup 1st International Contest] Hilbert Curve

A Hilbert curve is a recursively defined curve. An $n$-order Hilbert curve is defined on a $2^n \times 2^n$ grid. The 1st-order curve is as follows: :::align{center}  ::: The 2nd-order curve is as follows: :::align{center}  ::: The 3rd-order curve is as follows: :::align{center}  ::: An $n$-order Hilbert curve can be seen as a curve that starts from the lower-left corner, passes through all grid cells, and ends at the lower-right corner. We define the coordinates of the lower-left cell as $(0,0)$, and the coordinates of the lower-right cell as $(2^n - 1, 0)$. Then we can list, in order, the coordinates of the cells that the curve passes through. For example, the 1st-order Hilbert curve passes through the cells in the following order: $(0,0), (0,1), (1,1), (1,0)$. The 2nd-order Hilbert curve passes through the cells in the following order: $(0,0), (1,0), (1,1), (0,1), (0,2), (0,3), (1,3), (1,2), (2,2), (2,3), (3,3), (3,2), (3,1), (2,1), (2,0), (3,0)$. Given $n, p$, find the coordinates of the $p$-th point that the $n$-order Hilbert curve passes through.

The input contains one line with two integers $n, p$.

Output one line with two integers separated by a single space, representing the required coordinates.

### Constraints For $30\%$ of the testdata, $1 \le n \le 10$, $1 \le p \le 10^4$. For $50\%$ of the testdata, $1 \le n \le 30$, $1 \le p \le 10^6$. For all testdata, $1 \le n \le 100$, $1 \le p \le 10^{18}$. Translated by ChatGPT 5