Read problems statements in mandarin chinese, russian and vietnamese as well.

A tree is an undirected graph in which each pair of vertices is connected to each other by exactly one path. Weasel has a tree with N nodes. The indexing of the nodes is 0-based and the tree is rooted at node 0. Every node i has an initial value X_{0i}.

Every day d > 0, he performs the following operations, starting from the root:

Weasel computes X_{du} as the bitwise-xor sum of all the values X_{d − 1v} for a node v in u's subtree.
He recursively proceeds to perform the operation for every child of u.

For Q values of Δ, Weasel wants to compute X_{Δ0}.

------ Input ------

The first line of the input contains two integers N and Q.
Each of the following N − 1 lines contains two integers, u and v, an edge in the tree.
On the following line there are N integers, representing the X_{0} array.
Each of the next Q lines contains values for Δ as noted in the statement.

------ Output ------

You should print Q lines, each containing X_{Δ0}.

------ Constraints ------

$1 ≤ N, Q ≤ 2 * 10^{5}$
$0 ≤ X_{0i} ≤ 10^{18} for every 0 ≤ i ≤ N − 1.$
$0 ≤ Δ ≤ 10^{18}$
$0 ≤ u, v ≤ N − 1$

------ Subtasks ------

$Subtask 1 (20 points): 1 ≤ N ≤ 500 and Δ ≤ 500$
$Subtask 2 (20 points): 1 ≤ N ≤ 1000 and 1 ≤ N × Q ≤ 10^{6}$
$Subtask 3 (10 points): 1 ≤ N ≤ 5000$
$Subtask 4 (50 points): original constraints$
----- Sample Input 1 ------
4 3

0 1

1 2

0 3

1 5 8 7

1

2

3
----- Sample Output 1 ------
11

9

3

------ Explanation 0 ------

Initially X0 = [1, 5, 8, 7].
Weasel performs his operation on node 0:
X10 = X00 xor X01 xor X02 xor X03 = 1 xor 5 xor 8 xor 7 = 11.
X11 = X01 xor X02 = 5 xor 8 = 13.

X12 and X13 remain equal to X02, respectively X03.

见题面

见题面