Background

Cow Land is a special cow amusement park where cows can walk around, eat tasty grass, and visit different attractions (especially the roller coasters, which are very popular).

Problem Description

Cow Land has a total of $N$ different attractions ($2 \leq N \leq 10^5$). There are $N-1$ roads connecting pairs of attractions, which means there is exactly one simple path between any two attractions.

Each attraction $i$ has an enjoyment value $e_i$, and this value may change. This is because some attractions are more appealing in the morning, while others are more appealing in the afternoon.

Cows traveling from attraction $i$ to attraction $j$ can enjoy all the sights along the path from $i$ to $j$. The enjoyment value of this route is the bitwise XOR of the enjoyment values of all attractions on the path from $i$ to $j$ (including attraction $i$ and attraction $j$).

Please help the cows determine the enjoyment value of the routes they plan to take during their trip to Cow Land.

Input Format

The first line contains two integers $N, Q$ ($1 \leq Q \leq 10^5$).

The next line contains $N$ integers, where the $i$-th integer $e_i$ represents the enjoyment value of attraction $i$.

The next $N-1$ lines each contain two integers $a, b$, indicating that there is a road connecting attraction $a$ and attraction $b$.

The last $Q$ lines each contain 3 integers, describing an operation as follows.

1. 1 i v, meaning to change $e_i$ to $v$.
2. 2 i j, meaning to ask what the enjoyment value of the route from attraction $i$ to attraction $j$ is.

Output Format

For each operation of type 2, output the answer to the corresponding query.

5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3

21
20
4
20

Hint

Subtasks: For $50\%$ of the testdata, there are no update operations.

Translated by ChatGPT 5