Problem Description

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.

Input Format

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

Output Format

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

2 5

0 2

Hint

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