Description

The overall time limit for this problem is long, and submitting too many times may trigger the daily submission limit on Luogu. Please plan your submissions accordingly.

Shizuku gives you a tree with $n$ nodes, numbered $1 \sim n$. The $i$-th node has a weight $a_i$.

She asks you $q$ queries. Each query provides two nodes $x, y$. Let $p_i$ be the $i$-th node on the path from $x$ to $y$ (indexing starts from $0$). You need to compute:

$$\bigoplus_{i = 0}^{\mathrm{dis}(x, y)} (a_{p_i} + i)$$

Here, $\mathrm{dis}(x, y)$ is the number of edges on the path from $x$ to $y$, and $\oplus$ denotes the bitwise XOR operation.

Input Format

The first line contains two positive integers $n, q$.

The second line contains $n$ non-negative integers $a_1, \ldots, a_n$.

The next $n - 1$ lines each contain two positive integers $u, v$, indicating an edge between $u$ and $v$ in the tree.

The next $q$ lines each contain two positive integers $x, y$, representing a query.

Output Format

Output $q$ lines. The $i$-th line should contain a non-negative integer, which is the answer to the $i$-th query.

5 2
2 4 0 5 1
1 2
1 3
2 4
2 5
3 4
1 5

13
4

10 10
1 1 4 5 1 4 1 0 2 4
3 1
4 9
1 5
1 10
10 8
7 4
1 7
6 7
8 2
1 2
1 3
8 9
6 2
4 10
5 2
7 9
7 4
4 10
9 5

2
4
12
0
3
3
3
7
3
6

Hint

【Sample Explanation #1】

For the first query in sample one, $p = (3, 1, 2, 4)$. The answer is $(a_3 + 0) \oplus (a_1 + 1) \oplus (a_2 + 2) \oplus (a_4 + 3) = 0 \oplus 3 \oplus 6 \oplus 8 = 13$.

For the second query in sample one, $p = (1, 2, 5)$. The answer is $(a_1 + 0) \oplus (a_2 + 1) \oplus (a_5 + 2) = 2 \oplus 5 \oplus 3 = 4$.

【Data Range】

This problem uses bundled testing.

Subtask ID	$n,q \leq$	Special Properties	Score
$1$	$10^3$	None	$7$
$2$	$5 \times 10^4$	$a_i=0$	$9$
$3$		$a_i$ is a multiple of $2^{12}$	$17$
$4$		The tree is randomly generated$^\dagger$	$5$
$5$	$2 \times 10^5$	The tree is a chain	$16$
$6$	$5 \times 10^4$	None	$19$
$7$	$2 \times 10^5$		$27$

$\dagger$: The random generation method: for each $u$ from $2$ to $n$, uniformly randomly select an integer $v$ from $[1, u - 1]$, and add an edge between $u$ and $v$. Finally, the node labels are randomly shuffled.

For all test cases, $1 \le n,q \le 2 \times 10^5$, $1 \le x, y \le n$, $0 \le a_i \le n$. The given edges are guaranteed to form a tree.

Translated by DeepSeek V3.1