P5352 Terrible Homework

“As terrible as terrible homework.”

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.

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$.

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

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