Bracket Sequence Operations

You are given a bracket sequence of length \( n \) along with an associated weight for each bracket. Each bracket is represented by an integer \( a_i \) where \( a_i=1 \) represents a left bracket '(' and \( a_i=0 \) represents a right bracket ')'. The weight of the bracket at position \( i \) is given by \( b_i \).

For any bracket sequence, if you repeatedly remove a contiguous substring of the form \( () \) until no more removals can be made, the remaining sequence is uniquely determined. This sequence is called the unmatched bracket sequence. For example, consider the sequence with \( a_1=0,\; a_2=1,\; a_3=1,\; a_4=0,\; a_5=1 \). The original bracket sequence is: ') ( ( ) (' and its unmatched bracket sequence is ')((' (coming from positions 1, 2 and 5) with weights \( b_1, b_2, b_5 \).

There are \( m \) operations. Each operation is one of three types:

1. 1 x y: A point update. Flip the bracket at position \( x \) (i.e. assign \( a_x:=1-a_x \)) and update its weight to \( y \) (i.e. \( b_x:=y \)).
2. 2 l r: Query the subarray \( a[l..r] \). Let the unmatched bracket sequence determined by the deletion process be \( u_1, u_2, \dots, u_k \) with corresponding weights \( w_1, w_2, \dots, w_k \) (in the same order as they appear). Define the 32-bit bitwise NAND over the weights as follows: set \( c_0=2^{32}-1 \) and for each \( i=1,2,\dots,k \) compute \[ c_i = \text{NAND}(c_{i-1},w_i) = \left(~(c_{i-1} \& w_i)\right) \bmod 2^{32}, \] where the NAND operation is computed on 32-bit unsigned integers. If the unmatched bracket sequence is empty, then take the NAND result as \(2^{32}-1\) and the maximum value as 0. Let \( M \) be the maximum weight among unmatched brackets. The final answer for the query is \( (\text{NAND result}) \oplus M \) (where \( \oplus \) is the bitwise XOR).
3. 3 l r: Swap the segments \( a[l..r] \) and \( a[r+1..n] \); the weights \( b \) are swapped in the same way. In other words, if you denote the current sequence as \( a_1,a_2,\dots,a_n \) (and similarly for \( b \)), after this operation the sequence becomes \[ a_1,\dots,a_{l-1},\; a_{r+1},\dots,a_n,\; a_l,\dots,a_r, \] and similarly for \( b \).

Input Format:

• The first line contains two integers \( n \) and \( m \): the length of the sequence and the number of operations.
• The second line contains \( n \) integers representing \( a_1,a_2,\dots,a_n \) (each either 0 or 1).
• The third line contains \( n \) integers representing \( b_1,b_2,\dots,b_n \).
• The next \( m \) lines each describe an operation in one of the following formats:
  • 1 x y
  • 2 l r
  • 3 l r

Output Format:

• For each query operation (type 2), print the answer on a separate line.

Note: All indices are 1-indexed.

inputFormat

The input begins with a line containing two integers \( n \) and \( m \). Following that:

• A line with \( n \) integers \( a_1,a_2,\dots,a_n \) (each 0 or 1).
• A line with \( n \) integers \( b_1,b_2,\dots,b_n \).
• Then \( m \) lines, each representing an operation in one of the three formats described above.

outputFormat

For each operation of type 2, output the computed value on its own line.

sample

5 3
1 0 1 0 1
5 4 3 2 1
2 1 5
1 3 10
2 1 5

4294967295
4294967284