Problem Description

Given $n$ points and the value of each point, you are required to process the next $m$ operations. There are four types of operations, numbered from $0$ to $3$. Points are numbered from $1$ to $n$.

• 0 x y represents querying the $\text{xor}$ sum of the values of the points on the path from $x$ to $y$. It is guaranteed that $x$ and $y$ are connected.
• 1 x y represents connecting $x$ to $y$. If $x$ and $y$ are already connected, no action is needed.
• 2 x y represents deleting the edge $(x, y)$. The edge $(x, y)$ is not guaranteed to exist.
• 3 x y represents changing the value of point $x$ to $y$.

Input Format

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

The next $n$ lines, each containing one integer, represent the value of node $i$ at line $(i + 1)$.

The next $m$ lines, each containing three integers, represent the type of operation and the parameters required for the operation.

Output Format

For each operation of type $0$, you must output one line containing one integer, which is the $\text{xor}$ sum of the values of the points on the path from $x$ to $y$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
1

Input Sample #2

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

Output Sample #2

624
315
296
232709
232823

Notes

Data Size and Constraints

For all test cases, the following constraints apply:
- $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$, $1 \leq x, y \leq n$.
- For operation $3$, $1 \leq x \leq n$, $1 \leq y \leq 10^9$.

见题面 Input 部分

见题面 Output 部分