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.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Combinatorics

Range queries

Tree algorithms

Dynamic programming

Mathematics

Matrices

Data structures


Solutions:
def depth_dfs(u0=0):
	S = [u0]
	D = [-1] * N
	D[u0] = 0
	while S:
		u = S.pop()
		for v in G[u]:
			if D[v] < 0:
				D[v] = D[u] + 1
				S.append(v)
	return D

def one_value(X, t):
	res = 0
	for i in range(len(X)):
		if i & t - 1 == 0:
			res ^= X[i]

def dp_all_values(X, kmax):
	C = [X[:] for _ in range(kmax + 1)]
	for k in range(1, kmax + 1):
		for i in range(len(X)):
			C[k][i] = C[k - 1][i ^ 1 << k - 1]
			if i >> k - 1 & 1 == 0:
				C[k][i] ^= C[k - 1][i]
	return C

def main():
	global N, G
	(N, Q) = map(int, input().split())
	G = [[] for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	X0 = list(map(int, input().split()))
	D = depth_dfs()
	MD = max(D)
	X = [0] * (MD + 1)
	for u in range(N):
		X[D[u]] ^= X0[u]
	k = 1
	while 1 << k <= MD:
		k += 1
	period = 1 << k
	while len(X) < period:
		X.append(0)
	C = dp_all_values(X, k)
	for i in range(Q):
		t = (int(input()) - 1) % period
		print(C[k][t])
main()


from collections import defaultdict
from math import *

def getReducedGraph(G, N, XTable):
	visited = [0 for i in range(N)]
	Levels = [0 for i in range(N)]
	maxLevel = 0
	queue = [0]
	while queue:
		u = queue[0]
		visited[u] = 1
		queue.pop(0)
		if maxLevel < Levels[u]:
			maxLevel = Levels[u]
		for v in G[u]:
			if not visited[v]:
				Levels[v] = Levels[u] + 1
				queue.append(v)
	MaxPower = int(ceil(log(maxLevel + 1, 2)))
	Upto = 2 ** MaxPower
	newXTable = [0 for y in range(Upto)]
	for i in range(N):
		newXTable[Levels[i]] ^= XTable[i]
	for i in range(MaxPower):
		SkipAndDo = 2 ** i
		flag = 0
		for q in range(0, Upto, SkipAndDo):
			if flag == 0:
				flag = 1
				continue
			else:
				flag = 0
				for z in range(q, q + SkipAndDo):
					newXTable[z] ^= newXTable[z - SkipAndDo]
	revList = newXTable[1:]
	revList.reverse()
	return (newXTable[0:1] + revList, Upto)
(N, Q) = map(int, input().split())
G = defaultdict(list)
for i in range(N - 1):
	(u, v) = map(int, input().split())
	assert u < v
	G[u].append(v)
	G[v].append(u)
XTable = list(map(int, input().split()))
(newXTable, Upto) = getReducedGraph(G, N, XTable)
for i in range(Q):
	q = int(input())
	print(newXTable[q % Upto])


from collections import deque
(N, Q) = map(int, input().split())
g = [[] for i in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
X0 = list(map(int, input().split()))
A = [0] * N
P = 0
q = deque()
q.append((0, -1, 0))
while q:
	(u, p, d) = q.popleft()
	P = d
	A[d] ^= X0[u]
	for v in g[u]:
		if v != p:
			q.append((v, u, d + 1))
P += 1
B = P.bit_length()
P = 1 << P.bit_length()
A += [0] * (P - len(A))
for b in range(B):
	j = 1 << b
	j2 = j << 1
	for i in range(0, P, j2):
		L = A[i:i + j]
		R = A[i + j:i + j2]
		A[i:i + j] = [Lk ^ Rk for (Lk, Rk) in zip(L, R)]
		A[i + j:i + j2] = L
for q in range(Q):
	d = int(input())
	d = (d - 1) % P
	print(A[d])


import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
(N, Q) = map(int, input().split())
g = [[] for i in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
X0 = list(map(int, input().split()))
A = [0] * N
P = 0
q = deque()
q.append((0, -1, 0))
while q:
	(u, p, d) = q.popleft()
	P = max(P, d)
	A[d] ^= X0[u]
	for v in g[u]:
		if v != p:
			q.append((v, u, d + 1))
P += 1
A = A[:P]
P_ = 1 << P.bit_length()
if P_ != P << 1:
	P = P_
A += [0] * (P - len(A))
B = P.bit_length() - 1
for b in range(B):
	j = 1 << b
	j2 = j << 1
	for i in range(0, P, j2):
		L = A[i:i + j]
		R = A[i + j:i + j2]
		for k in range(j):
			A[i + k] = L[k] ^ R[k]
			A[i + k + j] = L[k]
for q in range(Q):
	d = int(input())
	d = (d - 1) % P
	print(A[d])


import math
import sys
from sys import stdin
from collections import deque
BIG = 2 ** 18
ANS = []
(N, Q) = list(map(int, sys.stdin.readline().strip().split(' ')))
graph = [[] for i in range(N)]
for _ in range(N - 1):
	(a, b) = list(map(int, sys.stdin.readline().strip().split(' ')))
	graph[a] += [b]
	graph[b] += [a]
value = list(map(int, sys.stdin.readline().strip().split(' ')))
query = []
for _ in range(Q):
	query += [int(input())]
parent = [-1] * N
level = [0] * N
q = deque([0])
while q:
	u = q.popleft()
	for v in graph[u]:
		if v != parent[u]:
			q.append(v)
			level[v] = level[u] + 1
			parent[v] = u
maxlevel = max(level)
LL = [[] for i in range(maxlevel + 1)]
for i in range(N):
	LL[level[i]] += [value[i]]
newvalue = [0] * (maxlevel + 1)

def find(C):
	temp = 0
	for i in range(len(C)):
		temp ^= C[i]
	return temp
for i in range(maxlevel + 1):
	newvalue[i] = find(LL[i])
newvalue = newvalue + [0] * (BIG - len(newvalue))

def findout(array):
	if len(array) == 2:
		return [array[0], array[1] ^ array[0]]
	if len(array) == 1:
		return [array[0]]
	left = array[:len(array) // 2]
	right = array[len(array) // 2:]
	ans1 = findout(left)
	ans2 = findout(right)
	ans = [0] * len(array)
	for i in range(len(array) // 2):
		if i == 0:
			ans[i] = ans1[i]
		else:
			ans[i] = ans1[i] ^ ans2[i]
	for i in range(len(array) // 2, len(array)):
		if i == len(array) // 2:
			ans[i] = ans1[0] ^ ans2[0]
		else:
			ans[i] = ans1[i - len(array) // 2]
	return ans
answers = findout(newvalue)
ANS = []
for i in range(len(query)):
	need = query[i] % BIG
	ANS += [answers[need]]
print('\n'.join(list(map(str, ANS))))