Description

Student $ben$ hates doing homework the most.

Now, the teacher has assigned $n$ homework tasks to $ben$. Each task has a difficulty value $A_i$.

At the beginning, every homework task is independent. There are some operations: each time, you add an edge between two tasks $x, y$ or delete an edge.

Because the teacher’s mood changes often, there are also operations that apply $xor$ with a value to the difficulty values of all tasks on the path between two tasks $x, y$.

Also, to satisfy $ben$’s curiosity, you need to answer, for all tasks on the path between $x, y$, the bitwise $and$ sum, bitwise $or$ sum, bitwise $xor$ sum, and the ordinary sum of difficulty values.

Input Format

The first line contains two positive integers $n, q$, representing the number of homework tasks and the number of operations.

The next line contains $n$ non-negative integers $A_1, ..., A_n$, representing the difficulty value of each task.

Then follow $q$ lines, each describing one operation:

• $L\ x\ y$: Add an edge between tasks $x$ and $y$. (It is guaranteed that no cycle will be formed, i.e. the graph is always a forest.)
• $C\ x\ y$: Delete the edge between $x$ and $y$. (It is guaranteed that this edge exists and will not be deleted more than once.)
• $U\ x\ y\ v$: Apply $xor$ with $v$ to the difficulty values of all tasks on the path between $x$ and $y$. (Including $x$ and $y$, and it is guaranteed that they are connected; the same applies below.)
• $A\ x\ y$: Query the bitwise $and$ sum of the difficulty values of all tasks on the path between $x$ and $y$.
• $O\ x\ y$: Query the bitwise $or$ sum of the difficulty values of all tasks on the path between $x$ and $y$.
• $X\ x\ y$: Query the bitwise $xor$ sum of the difficulty values of all tasks on the path between $x$ and $y$.
• $S\ x\ y$: Query the ordinary sum of the difficulty values of all tasks on the path between $x$ and $y$.

Output Format

For each $A, O, X, S$ operation, output the answer.

4 10
1 2 3 4
L 1 2
L 2 3
L 2 4
A 1 4
U 3 4 2
O 1 4
C 2 4
L 3 4
X 1 4
S 1 3

0
7
6
2

Hint

For $10\%$ of the testdata, $n = 100, q = 100$.

For another $10\%$ of the testdata, $n = 5000, q = 5000$.

For another $20\%$ of the testdata, $n = 10000, q = 10000$.

For $100\%$ of the testdata, $2 \le n, q \le 100000$, $0 \le A_i < 2^{30}$.

Translated by ChatGPT 5