Background

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.

Problem Description

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

Input Format

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.

Output Format

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

5 2
665667089 948925818 1118302620 288255565 1682529647 
5 2
1 3 4
3 1
2 3 5
2 2 4
3 4
5 25
1 3 3
1 3 4
3 1
2 1 5
2 1 3

665667089
288255566
665667089

Hint

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