Description

Given $n$ nodes and each node’s weight, you need to process the next $m$ operations.
There are four types of operations, numbered from $0$ to $3$. Nodes are numbered from $1$ to $n$.

• 0 x y asks for the $\text{xor}$ sum of the weights of the nodes on the path from $x$ to $y$. It is guaranteed that $x$ and $y$ are connected.
• 1 x y connects $x$ to $y$. If $x$ and $y$ are already connected, do nothing.
• 2 x y deletes the edge $(x, y)$. The existence of edge $(x, y)$ is not guaranteed.
• 3 x y sets the weight of node $x$ to $y$.

Input Format

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

The next $n$ lines each contain one integer. On the $(i + 1)$-th line, the integer $a_i$ denotes the weight of node $i$.

The next $m$ lines each contain three integers, representing the operation type and its parameters.

Output Format

For each operation of type $0$, output one line with one integer, the $\text{xor}$ sum of the node weights on the path from $x$ to $y$.

3 3 
1
2
3
1 1 2
0 1 2 
0 1 1

3
1

5 14
114
514
19
19
810
1 1 2
0 1 2
2 1 2
1 1 2
1 2 3
2 1 3
1 1 3
1 4 5
1 2 5
0 3 5
0 3 4
3 5 233333
0 1 5
0 2 5

624
315
296
232709
232823

Hint

Constraints and Conventions

For all testdata, it is guaranteed that:

• $1 \leq n \leq 10^5$, $1 \leq m \leq 3 \times 10^5$, $1 \leq a_i \leq 10^9$.
• For operations $0, 1, 2$, it holds that $1 \leq x, y \leq n$.
• For operation $3$, it holds that $1 \leq x \leq n$, $1 \leq y \leq 10^9$.

Translated by ChatGPT 5