P4991 Angry XiaoX

### For Q&A, please go to https://www.luogu.org/discuss/show?postid=79498. A few days ago, in a mock contest, $XiaoX$ got $AK$ again and again. He wanted to make things harder for everyone, so he created the following problem.

Given a sequence, you need to maintain the following operations: $1$ $l$ $r$ $k$: bitwise NOT the last $k$ bits of the numbers from $l$ to $r$. $2$ $l$ $r$ $k$: reverse the last $k$ bits of the numbers from $l$ to $r$. $3$ $w$: query the value at position $w$. To reduce the difficulty of this problem, we make the following rules: For operations on the sequence, the $k$ values are fixed within a certain range. There are a total of $t$ different $k$ values. After each $k$, there are some operations. In these operations, the $k$ (the number of modified bits) is the same. ### Definition of bitwise NOT: For example, the binary representation of a number is: ``` 10100111 ``` After taking bitwise NOT on the last 5 bits, it becomes: ``` 10111000 ``` ### Definition of reverse: For example, the binary representation of a number is: ``` 10100111 ``` After reversing the last 5 bits, it becomes: ``` 10111100 ```

The first line contains two integers $n$ and $t$, representing the length of the sequence and the number of $k$ values. The second line contains $n$ numbers, representing the initial sequence. Then follow $t$ groups of operations. For each group, the first line contains two numbers $q_i$ and $k_i$, representing the number of operations and the value of $k$ used in these operations. The next $q_i$ lines describe the operations in this group.

For each operation of type $3$, output one line with one integer, representing the answer.

For $10\%$ of the data, there are no operations of type $1$ or $2$. For another $10\%$ of the data, there are no operations of type $1$. For another $10\%$ of the data, there are no operations of type $2$. For $50\%$ of the data, $t \le 1$. For $70\%$ of the data, $t \le 2$. For $100\%$ of the data, $t \le 5$, $1 \le n \le 50000$, $1 \le q_i \le 20000$, $k \le 25$. The initial sequence is generated by $rand() * rand()$ (on Windows). Thanks to @swhsz for verifying the problem. Translated by ChatGPT 5