Given $n$ points and the weight of each point, you are to process $m$ operations.

There are four types of operations, numbered from $0$ to $3$. Points are numbered from $1$ to $n$.

• 0 x y: Query the $\text{xor}$ sum of the weights of the points on the path between $x$ and $y$. If the path does not exist, output $-1$.
• 1 x y: Connect $x$ and $y$. If $x$ and $y$ are already connected, no action is needed.
• 2 x y: Delete the edge $(x, y)$. It is not guaranteed that the edge $(x, y)$ exists.
• 3 x y: Change the weight of point $x$ to $y$.

Input

The first line contains two integers $n$ $(1 \leq n \leq 150,000)$ and $m$ $(1 \leq m \leq 300,000)$, representing the number of points and the number of operations, respectively.

The next $n$ lines each contain an integer in the range $[1, 10^9]$, representing the weight of each point.

Then follow $m$ lines, each containing three integers representing the operation type and the required parameters.

Output

For each operation of type $0$, output a single integer on a new line representing the $\text{xor}$ sum of the weights of the points on the path between $x$ and $y$. If the path does not exist, output $-1$.

Examples

Input 1

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

Output 1

3
1

Input 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 2

624
315
296
232709
232823

Input 3

10 50
44 
61 
37 
67 
60 
1 
68 
68 
70 
69 
1 8 2
1 5 3
1 2 1
1 9 8
1 1 1
1 3 2
1 2 1
1 8 2
1 3 1
1 1 1
0 10 6
3 9 98
3 2 35
0 9 7
3 6 36
1 9 1
0 10 6
1 3 1
1 4 1
0 7 6
3 1 39
3 7 38
1 8 3
0 4 1
3 1 51
1 8 1
1 2 1
1 4 1
1 4 2
1 8 1
1 10 8
2 4 1
0 6 5
3 8 57
2 5 1
1 9 2
2 8 6
0 10 1
0 4 1
2 4 1
3 6 96
0 6 2
0 3 1
1 1 1
3 5 50
1 5 1
0 3 1
2 6 1
2 5 1
1 10 9

Output 3

-1
-1
-1
-1
100
-1
108
-1
-1
53
53