Description

LYK喜欢玩游戏，它找到一棵有 n个节点的树，打算在这棵树上面玩游戏。 首先它在所有节点上都规定一个点权 ai，然后它选择从一个点 A出发，经过最短路到达点B并记录下所经过的所有点的点权，LYK将会得到这些点权的异或和的开心值。 LYK想得到更多的开心值，于是它把所有不同点对 A，B(共 n*(n-1)对)所得到的开心值累加起来，作为LYK最终的开心值。于是 LYK想让你帮它计算出它最终的开心值是多少。

不过这个问题看起来十分easy。于是LYK共有Q次修改的机会，每次它会选择一个点X， 将它的点权修改为Y。你需要计算出每次修改完成后 LYK 最终的开心值。

Format

Input

第一行两个整数n,Q。

接下来一行n个数ai，表示这棵树中所有点初始点权。

接下来n-1 行，每行两个数 u,v表示存在一条边连接 u,v两个点。

接下来Q行，每行两个数X,Y 表示对于这次修改操作，将第X个点的点权修改成 Y。

对于100%的数据：

n,Q<=10000，0<=任意时刻任意点的点权<32768，点权随机。

其中均匀分布着50%的数据树是随机的。

Output

输出共Q行，每行表示修改完之后 LYK最终的开心值。

Samples

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