Parenthesis sequence

题号：NC210598
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

You are given a $01$ sequence $a_1a_2\dots a_n$ representing a parenthesis sequence. When $a_i=1$ , it means there is a left parenthesis(in $i$ -th position. When $a_i=0$ , it means there is a right parenthesis)in $i$ -th position. There is also a weight sequence $b_1, b_2, \dots, b_n$ .

For a given parenthesis sequence, you get a unique sequence by deleting substring()until no matching parenthesis left. We call it as the unmatched parenthesis sequence. For example, the parenthesis sequence is)(()(, its unmatched parenthesis sequence is)((, where the position is $1, 2, 5$ .

There are $m$ operations in three types:

1 x y, change $a_x$ to $1-a_x$ , and $b_x$ to $y$ .
2 l r, For those $i$ such that $a_i$ is an unmatched parenthesis in $a[l\dots r]$ , you are asked to calculate the $\texttt{max}$ and $\texttt{NAND}$ of all $b_i$ . You only need to output the $\texttt{xor}$ of the two results. Assume $\texttt{max} = 0$ and $\texttt{NAND} = 2^{32} - 1$ if there's no such $i$ .

For two unsigned int $a,b$ , $\texttt{NAND}$ of them is~(a&b)(in C++ code). For a sequence $b_1, b_2, \dots, b_n$ , $\texttt{NAND}$ are computed from left to right. That is, $c_0=2^{32}-1, c_{i}=\texttt{NAND}(c_{i-1}, b_i)$ . The result is $c_n$ .
3 l r, swap $a[l\dots r]$ with $a[r+1\dots n]$ , swap $b[l\dots r]$ with $b[r+1\dots n]$ .

输入描述:

The first line contains two integers .
Each line of the following n lines contains two integers .
Each line of the following m lines contains an operation : , , .

输出描述:

For each of the second operation, output the answer.

示例1

输入

复制

输出

复制

4294967295
4294967284
4294967281