Homework Graph Queries

Ben hates doing homework. Now, his teacher has assigned him n homework pieces, each with a difficulty value \(A_i\). Initially, every homework is independent (i.e. there are no connections between them).

You are given \(q\) operations. There are three types of operations:

• Add/Delete Edge: Either add an edge between two homework pieces \(x\) and \(y\) with the command ADD x y, or delete the edge between them with DEL x y.
• Path XOR Update: Given two homework pieces \(x\) and \(y\) and an integer \(v\), update every homework on the unique path from \(x\) to \(y\) by applying a bitwise XOR with \(v\) (i.e. set \(A_i = A_i \oplus v\) for each homework on the path). The command is XOR x y v.
• Path Query: Given two homework pieces \(x\) and \(y\), query the homework on the unique path between them. You need to compute and output four values, in order:
  1. The bitwise AND of all the difficulties on the path, i.e. \(A_{i_1} \& A_{i_2} \& \cdots \& A_{i_k}\).
  2. The bitwise OR of all the difficulties on the path, i.e. \(A_{i_1} | A_{i_2} | \cdots | A_{i_k}\).
  3. The bitwise XOR of all the difficulties on the path, i.e. \(A_{i_1} \oplus A_{i_2} \oplus \cdots \oplus A_{i_k}\).
  4. The sum of all the difficulties on the path, i.e. \(A_{i_1} + A_{i_2} + \cdots + A_{i_k}\).
  The command is QUERY x y.

It is guaranteed that for each XOR or QUERY operation, there exists a unique path between \(x\) and \(y\).

inputFormat

The input begins with a line containing two integers \(n\) and \(q\) — the number of homework pieces and the number of operations, respectively.

The second line contains \(n\) integers \(A_1, A_2, \ldots, A_n\), representing the initial difficulty values.

Then \(q\) lines follow, each line representing one operation in one of the following formats:

• ADD x y: Add an edge between homework pieces \(x\) and \(y\).
• DEL x y: Delete the edge between homework pieces \(x\) and \(y\).
• XOR x y v: For the unique path from \(x\) to \(y\), update every difficulty \(A_i = A_i \oplus v\).
• QUERY x y: For the unique path from \(x\) to \(y\), output four space-separated integers representing the bitwise AND, bitwise OR, bitwise XOR, and the sum of the difficulties on that path.

outputFormat

For each QUERY operation, output a single line with four space-separated integers: the bitwise AND, the bitwise OR, the bitwise XOR, and the sum of the difficulties along the path, in that order.

sample

5 6
1 2 3 4 5
ADD 1 2
ADD 2 3
QUERY 1 3
XOR 2 3 2
QUERY 1 3
ADD 3 4
QUERY 1 4

0 3 0 6
0 1 0 2
0 5 4 6