In graph theory, if an undirected gragh G(V, E) without cycle has n vertices, n − 1 edges and the graph is connected, then G(V, E) is called a tree.
You are given a tree has n vertices, each vertice has a weight. Vertice i's weight is
. Henry has q queries, each query has two vertices u, v. He wants to know the xor sum of the weights of all vertices on the shortest path from u to v (contains u,v).

输入描述:

The first line is an integer , the number of the vertices.
Line 2 has n integers , the ith integer is  
, the weight of the vertice i.
Line 3 to line n+1, each line has two integers u, v, means there has an edge between u and 
Line n + 1 is q, means the number of queries.
Next  lines, each line has two integers u, v (1 ≤ u, v ≤ n) means the beginning and end of
the shortest path henry wants to query.

输出描述:

For each query,output the xor sum of the weights of all vertices on the shortest path from u to v.

6
1 1 2 3 4 10
1 2
1 3
1 4
2 5
2 6
2
3 6
2 4

8
3