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

For any bracket sequence, by repeatedly deleting substrings of the form "()", one can eventually obtain a unique sequence called the unmatched bracket sequence. For example, if $a_1=')', a_2='(', a_3='(', a_4=')', a_5='('$, the unmatched bracket sequence is ")((", and the corresponding positions are $1, 2, 5$. The weights of these unmatched brackets are $b_1, b_2, b_5$.

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

1 x y: Perform a point modification: $a_x := 1 - a_x$; $b_x := y$.

2 l r: Calculate the $\texttt{NAND}$ (32-bit bitwise NAND, see https://en.wikipedia.org/wiki/NAND_logic) and the $\texttt{max}$ (maximum value) of the weights $b$ of the unmatched brackets in the range $a[l..r]$ from left to right, then output the result of their $\texttt{xor}$. If the unmatched bracket sequence is empty, the $\texttt{NAND}$ result is $2^{32}-1$ and the $\texttt{max}$ result is $0$.

$\texttt{NAND}$ is defined as follows: starting with $c_0 = 2^{32}-1$, then sequentially $c_i = \texttt{NAND}(c_{i-1}, b_i)$. For a sequence of $n$ values $b$, the final answer is $c_n$.

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

Input

The first line contains two space-separated integers $n$ and $m$.

The next $n$ lines each contain two space-separated integers, where the $i$-th line contains $a_i$ and $b_i$.

The next $m$ lines each represent an operation.

Output

For each type 2 operation, output one line containing the answer.

Examples

Input 1

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

Output 1

4294967295
4294967284
4294967281

Subtasks

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

For $100\%$ of the data:

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