Folding Sheets

You have a sheet of grid paper of size $N \times N$ squares. $N$ is a power of two.

The squares are numbered from $1$ to $N^2$, the top row first and left to right inside each row. Each square holds only its own number.

The sheet is folded in half over and over. The bottom half is folded over the top half first, then the right half over the left half, and the two moves alternate in that order until the folded sheet is $1 \times 1$.

The squares then form a column of size $1 \times 1 \times N^2$. Reading that column from its bottom square to its top square gives the sequence $S = \langle S_1, S_2, \ldots, S_P, \ldots, S_{N^2} \rangle$, where $P$ is the position in the sequence.

A developer sitting through a dull meeting folds sheets into such columns and wants answers to two questions.

• Question type 1. A number $X$ is given. At which position $P$ of the sequence $S$ does it sit?
• Question type 2. A position $P$ of the sequence $S$ is given. Which number $X$ sits there?

Write a program that computes the number $X$ or the position $P$, depending on the type of the question.

The first line contains the number of questions $Q$. Each of the next $Q$ lines contains three integers $T$, $K$, $V$, separated by a single space.

• $T$ is the type of the question. $T = 1$ or $T = 2$.
• $K$ is the exponent that fixes the size of the sheet. The sheet is $N = 2^K$ squares wide.
• $V$ is the number $X$ when $T = 1$, and the position $P$ when $T = 2$.

Print $Q$ lines, one per question. Each line holds a single integer, the position $P$ or the number $X$, depending on the type of the question.

• $1 \le Q \le 10000$
• $1 \le T \le 2$
• $0 \le K \le 31$
• $1 \le X, P \le N^2$, where $N = 2^K$

For $N = 2$, reading the column from bottom to top gives $S = \langle 1, 3, 4, 2 \rangle$.

For $N = 4$, $S = \langle 1, 13, 16, 4, 8, 12, 9, 5, 6, 10, 11, 7, 3, 15, 14, 2 \rangle$.