Sequence Transformation Maintenance

You are given an array A of length \(2^n\), indexed from \(0\) to \(2^n-1\). Initially, for every index \(i\) the value is \(A[i]=i\). You must process \(m\) operations on the sequence. There are three types of operations:

• Operation 1: Form two subsequences: let \(a\) be the subsequence of all elements at even indices and \(b\) be the subsequence of all elements at odd indices. Then update \(A\) to be the concatenation \(a\) followed by \(b\). Formally, if the current array is \(\{a_0, a_1, \ldots, a_{2^n-1}\}\), then after this operation the new array becomes \[ \{a_0, a_2, \ldots, a_{2^n-2},\; a_1, a_3, \ldots, a_{2^n-1}\}. \] Equivalently, if you denote \(N=2^n\), then the new array at index \(x\) becomes \[ A_{new}[x] = \begin{cases} A[2x] & \text{if } 0 \le x < N/2, \\ A[2(x-N/2)+1] & \text{if } N/2 \le x < N. \end{cases} \]
• Operation 2: Form two subsequences: let \(a\) be the subsequence of all elements at odd indices and \(b\) be the subsequence of all elements at even indices. Then update \(A\) to be the concatenation \(a\) followed by \(b\). That is, the new array becomes \[ \{a_1, a_3, \ldots, a_{2^n-1},\; a_0, a_2, \ldots, a_{2^n-2}\}. \] In formula, for \(0 \le x < N\), \[ A_{new}[x] = \begin{cases} A[2x+1] & \text{if } 0 \le x < N/2, \\ A[2(x-N/2)] & \text{if } N/2 \le x < N. \end{cases} \]
• Operation 3: A query: given an index \(x\), output the value at index \(x\) in the current array.

You are guaranteed that the total number of operations equals \(m\). Note that the operations are applied sequentially and affect the ordering of the whole sequence.

Hint: Instead of simulating the entire array (which may be huge), notice that the operations have a special structure. In fact, if you represent the index \(x\) in binary using \(n\) bits, each reordering operation essentially rotates the binary representation by one bit. Operation 1 appends the most significant bit (MSB) unchanged, and Operation 2 appends its flipped value. Use this observation to compute the answer for each query efficiently.

inputFormat

The first line contains two integers \(n\) and \(m\) (where the array length is \(2^n\)). Each of the next \(m\) lines represents an operation in one of the following formats:

• If the operation is of type 1, the line contains a single integer: 1.
• If the operation is of type 2, the line contains a single integer: 2.
• If the operation is a query (type 3), the line contains two integers: 3 x, which means query the value at index \(x\) (0-indexed).

outputFormat

For each query operation (type 3), output a single line containing the answer.

sample

2 5
1
3 0
2
3 1
3 0

0
3
2