Sleeping Difficulty Syndrome

You are given a chain of n nodes (indexed from 1 to n). Each node i is associated with a bitwise operation opt_i and an integer x_i. The operation is one of the following:

• if opt_i = 1: perform bitwise AND, i.e. $$v = v \mathbin{\&} x_i$$
• if opt_i = 2: perform bitwise OR, i.e. $$v = v \mathbin{|} x_i$$
• if opt_i = 3: perform bitwise XOR, i.e. $$v = v \oplus x_i$$

You need to process q operations on this chain. There are two types of operations:

1. Query operation (denoted by the letter Q): Given three integers x, y, and z, you are to choose an initial integer v from the range \([0,z]\) such that after sequentially applying the operations from node x to node y (in increasing order), the final value is maximized. In other words, if the function f is defined by
   
   $$f(v)= (\cdots((v\; opt_x\; x_x)\; opt_{x+1}\; x_{x+1})\cdots opt_y\; x_y),$$
   
   find the maximum possible value of f(v) with \(0 \le v \le z\).
2. Modify operation (denoted by the letter M): Given three integers x, y and z, update the node at position x so that its operation becomes y and its associated integer becomes z.

Note: All indices in the operations are 1-indexed.

inputFormat

The first line contains two integers n and q, representing the number of nodes and the number of operations respectively.

The next n lines each contain two integers opt and x describing the operation and the associated number for each node. Here, opt is 1, 2, or 3 corresponding to bitwise AND, OR, and XOR respectively.

Then, q lines follow, each describing an operation. Each operation line starts with a character:

• If it is a query operation, the line is in the format: Q x y z
• If it is a modify operation, the line is in the format: M x y z

outputFormat

For each query operation, output a single line containing the maximum final value obtainable by choosing an appropriate initial value v from \([0,z]\) and applying the operations from node x to node y sequentially.

sample

5 5
1 5
2 3
3 7
1 2
2 8
Q 1 3 10
M 2 3 4
Q 2 5 7
M 5 1 6
Q 1 5 5

4
10
2