Problem Description

Given a bracket sequence of length $n$. Each position has a bracket $a_i$, where $a_i=1$ means a left bracket '(', and $a_i=0$ means a right bracket ')'. The bracket at position $i$ has a weight $b_i$.

For any bracket sequence, by repeatedly deleting a substring of the form '()' until no more operations can be done, you will finally get a unique sequence. This sequence is called the unmatched brackets. For example, $a_1=')',a_2='(',a_3='(',a_4=')',a_5='('$: the unmatched bracket sequence is $')(('$, and the positions of these unmatched brackets are $1,2,5$. The corresponding $b$ values are $b_1,b_2,b_5$.

There are $m$ operations, of the following three types:

1 x y: Single-point modification, i.e. $a_x:=1-a_x; b_x:=y$.

2 l r: For the unmatched bracket positions in $a[l..r]$, take the $\texttt {NAND}$ from left to right ($32$-bit bitwise NAND; see https://en.wikipedia.org/wiki/NAND_logic), and also take the $\texttt {max}$ (maximum value). Output the result of $\texttt {xor}$ between these two values. If the unmatched brackets form an empty sequence, then the answer for $\texttt {NAND}$ is $2^{32}-1$, and the answer for $\texttt {max}$ is $0$.

$\texttt {NAND}$ means starting with $c_0=2^{32}-1$, then in order $c_i=\texttt {NAND}(c_{i-1},b_i)$. For a sequence $b$ with $n$ values, the final answer is $c_n$.

3 l r: Swap $a[l..r]$ and $a[r+1..n]$. Do the same operation on $b$.

Input Format

The first line contains two integers $n,m$ separated by spaces.

Then $n$ lines follow, each containing two integers separated by spaces. The $i$-th line is $a_i,b_i$.

Then $m$ lines follow, each describing one operation.

Output Format

For each operation of type $2$, output one line with the answer.

10 10
0 1
1 9
1 2
0 5
1 1
0 6
1 1
0 4
0 8
1 7
2 5 7
3 1 10
1 1 3
2 1 3
3 2 9
3 4 10
3 7 8
1 10 2
3 3 4
2 5 7

4294967295
4294967284
4294967281

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477.

For $100\%$ of the testdata,

$0 \le a[i] \le 1$.

$0 \le b[i] \le 10^9$.

$1 \le n \le 2\times10^6,1 \le m \le 2\times10^5$。

Translated by ChatGPT 5