问题描述
pog在与szh玩游戏，这一次，pog又找到了一棵树，与之前的树不同的是，这棵树上的所有节点都有一个权值！第$i$个节点的权值为$a_i$。Pog与szh在树上选择两个不同的点，然后pog沿着树上的路径走向szh，并记下走过的点的权值，然而不幸的是，点实在是太多了，pog为了简便，只记录经过的所有点的权值的异或和。出于szh对pog的爱，szh想知道对于任意的$n*(n-1)$种不同的组合，pog所记录的值的和是多少。由于pog已经厌倦了szh的毫无新意的追求，他会在每个时刻将aA改变成B，szh当然得输出所有时刻的答案。
输入描述
若干组数据(不超过$3$组$n \geq 1000$)。
每组数据第一行两个整数$n(1 \leq n \leq 10000)$，$Q(1 \leq Q \leq 10000)$。
接下来一行$n$个整数$a_i(0 \leq ai < 32768)$。
接下来$n-1$行，每行两个数$b_i,c_i$,表示存在一条边连接$b_i$与$c_i$。
接下来$Q$行，每行两个数$A(1 \leq A \leq n)$，$B(0 \leq B < 32768)$，表示将aA修改成B
输出描述
对于每组数组的每个询问，输出一行，表示对于每种不同的状态pog所记录的值的和。
输入样例
5 5
1 2 3 4 5
1 2
1 3
2 4
2 5
1 3
2 4
4 4
5 3
2 1
输出样例
82
46
46
70
60
