Description

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.

Input Format

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$.

Output Format

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

2 7
2 0
1 0
2 1
1 1
2 2
1 0
2 3

0
2
0
1

Hint

Sample Explanation

The sequence from left to right before and after all operations is as follows:

The number at index $0$ is $0$.

The number at index $1$ is $2$.

The number at index $2$ is $0$.

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<2^n$.

Translated by ChatGPT 5