P7442 "EZEC-7" Maintain the Sequence

[](https://www.luogu.com.cn/paste/tdqr0sto) Poor dead_X could not get the song, so he made an easy problem and gave the contestants $100$ points. 2022 Update: The song has been received, and the problem is very easy.

You need to maintain a sequence. At the beginning, the sequence has $2^n$ numbers, indexed starting from $0$. The initial value of the $i$-th number is $i$. You need to support the following three operations: - Define $a$ as the subsequence consisting of all elements whose indices are even, and define $b$ as the subsequence consisting of all elements whose indices are odd. Concatenate $a$ and $b$ to form a new sequence. - Define $a$ as the subsequence consisting of all elements whose indices are odd, and define $b$ as the subsequence consisting of all elements whose indices are even. Concatenate $a$ and $b$ to form a new sequence. - Query the number at index $x$. In total, there will be $m$ operations.

The first line contains two positive integers $n,m$. Then there are $m$ lines. Each line contains two non-negative integers $op,x$, representing one operation. If $op=1$, then if $x=0$ it means the first operation, and if $x=1$ it means the second operation. If $op=2$, it means the third operation, and the parameter $x$ is the queried index $x$.

For each $op=2$, output one line, which is the corresponding number.

**Sample Explanation** The sequence from left to right before and after all operations is as follows: $$\{0,1,2,3\}$$ The number at index $0$ is $0$. $$\{0,2\},\{1,3\}$$ $$\{0,2,1,3\}$$ The number at index $1$ is $2$. $$\{2,3\},\{0,1\}$$ $$\{2,3,0,1\}$$ The number at index $2$ is $0$. $$\{2,0\},\{3,1\}$$ $$\{2,0,3,1\}$$ The number at index $3$ is $1$. **Constraints** **This problem uses bundled testdata.** - Subtask 1 (10 points): There is no operation with $op=1$. - Subtask 2 (10 points): $n\leq 10，m\leq 10^3$. - Subtask 3 (20 points): $n\leq 10$. - Subtask 4 (20 points): $m\leq 10^3$. - Subtask 5 (20 points): For operations with $op=1$, $x=0$. - Subtask 6 (20 points): No special restrictions. For $100\%$ of the data, $1\leq n\leq 32$，$1\leq m\leq 10^6$. If $op=1$, then $x\in\{0,1\}$. If $op=2$, then $0\leq x