Description

现有一棵 $n$ 个点的有根树，节点 $1$ 是根。初始每个点有一个 $w_i$ 的点权。

定义一次操作是对于树上的每个点 $i$，令其点权变成操作前其子树内所有点（包括点 $i$）的点权的异或和。

现有 $q$ 次询问，每次询问包含一个数 $t_i$，需要求出初始状态下进行 $t_i$ 次操作后根节点的点权。

Input

第一行两个正整数 $n,q$ ($1\le n,q\le 2\times 10^5$)，代表树的节点数和询问数。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$ ($1\le u_i,v_i\le n$)，描述一条连接 $u_i$ 和 $v_i$ 的树边。

接下来一行，共 $n$ 个整数 $w_1,w_2,\ldots,w_n$ ($0\le w_i\le 10^9$)，代表每个点的初始点权。

接下来 $q$ 行，每行一个整数 $t_i$ ($0\le t_i\le 10^9$)，代表每次询问对初始状态的操作次数。

Output

输出 $q$ 行，每行一个正整数，代表操作相应次数后根节点的点权。

Samples

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

1
7

Note

对于样例，初始状态进行一次操作后节点的点权分别为 $[1,0,2,1,5]$，进行两次操作后节点点权分别为 $[7,6,6,4,5]$。

Resources

The 22nd UESTC Programming Contest Preliminary