Dis

Problem Description

You are given a tree of $n$ vertices, each with its own vertex weight. Answer multiple queries: for each query, output the XOR sum of the vertex weights on the set of vertices lying on the simple path between two given vertices.

Input Format

The first line contains two integers $n$ and $m$, where $n$ is the number of vertices and $m$ is the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, the vertex weights.

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

The following $m$ lines each contain two integers $u, v$, representing a query: the XOR sum of the vertex weights on the simple path from $u$ to $v$.

Output Format

Output $m$ lines, one integer per query, in order.

Sample Input

7 3
0 1 2 3 4 5 6
1 2
1 3
2 4
2 5
3 6
3 7
4 6
4 7
5 6

Sample Output

5
6
2

Constraints

$1 \le n, m \le 200000$, $1 \le a_i \le 10^6$.