Dynamic Forest XOR Queries

You are given n nodes, numbered from 1 to n, each with an initial weight. Then you are given m operations to process. There are 4 types of operations, labeled from 0 to 3. The operations are defined as follows:

• 0 x y: Query the path from node x to node y (it is guaranteed that x and y are connected) and output the XOR-sum of the weights along the path. Formally, if the weights on the path are \(w_1, w_2, \dots, w_k\), output \(w_1 \oplus w_2 \oplus \cdots \oplus w_k\) where \(\oplus\) denotes the bitwise XOR operation.
• 1 x y: Connect node x with node y. If they are already connected, do nothing.
• 2 x y: Delete the edge between node x and node y if it exists. (If it does not exist, do nothing.)
• 3 x y: Change the weight of node x to y.

Note: The operations maintain a forest structure. It is guaranteed that whenever a query (operation 0) is issued, there exists a path between the specified nodes.

inputFormat

The first line contains two integers n and m — the number of nodes and the number of operations.

The second line contains n integers, where the i-th integer represents the initial weight of node i.

Each of the following m lines contains an operation in one of the following formats:

• 0 x y
• 1 x y
• 2 x y
• 3 x y

outputFormat

For each operation of type 0, output a single line with one integer: the XOR-sum of all node weights on the path from x to y.

sample

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

0
8