题目描述

给定一棵由$n$个结点构成的树，结点编号为$1$～$n$，其中$1$号点为树根，第$i$个点的点权为$a_i$。

对于整棵树的第$k$次操作，我们会从根结点开始进行下面的操作：

对于结点 $u$，计算其子树中每个节点 $v$ 在前一次操作后的权值 $A_{v}^{(k-1)}$的异或和，并记为 $u$ 在这一次操作后的权值 $A_u^{(k)}$，对于结点 $u$ 的每个儿子，递归进行上述计算。

现对于给定的 $q$ 次询问，每次询问一个操作数 $m$ ，请你求出 $m$ 次操作后， 根结点的值（即$A_1^{(m)}$ 的值）。

输入格式

输入第一行：两个正整数$n,q$ 输入第二行：$n$个正整数$a_1,a_2,...,a_n$，分别表示一开始每个点的点权。 接下来$n-1$行，每行两个正整数$u_i,v_i$，表示第$i$条边连接$u_i,v_i$两点。 最后一行，$q$个正整数，分别表示询问的操作数$m_i$。

输出格式

输出共一行：$q$个正整数，分别表示每次询问的$m_i$轮操作后，根结点的值。

4 3
1 5 8 7
2 3
1 4
1 2
1 2 3

11 9 3

数据范围

• 对于$30\%$的数据，$1\leq n,q,m_i \leq 100$；

• 对于$60\%$的数据，$1\leq n \leq 1000, 1\leq n \times q \leq 10^6$；

• 对于$100\%$的数据，$1\leq n,q \leq 2\times 10^5, 1\leq m_i,a_i \leq 10^{18}$