记忆
题号：NC274793
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

我做好了挨一击番茄炒蛋拳的准备，可是伊娜三步并作两步窝到沙发里，自顾自地刷起手机，我轻轻走到沙发旁，半跪着，她却别过脸。

“骗子。”她说。

风铃在响着，心嘭嘭直跳，初夏的微风不合时宜地吹进房间里，吹飞了她精心点缀的手账，吹乱了她如绢如丝的秀发，也吹散了我的思绪。我要告诉她，告诉这个傻姑娘，她才是……

但未卜先知般，伊娜转过身，用食指轻抵住了我的嘴。

她在笑，是月牙一般的笑，是一抹在我将来的岁月里都难以忘记的浅笑。坏了，她全都知道。


在记忆里，小 L 有一棵 n 个点的树，第 i 个点有一个点权 a_i。

接下来小 L 共想起了 m 个事件，在每个事件里小 L 会有一个初始记忆值 x，她要在树上从点 u 沿简单路径走到点 v。当她经过任意一条边时，她的记忆值会增加 1；当她到达任意节点 i 时（包括 u 和 v），她的记忆值会异或上 a_i。

小 L 想知道每个事件结束时她的记忆值。

输入描述:

第一行两个正整数 n,m，表示树的节点数和事件的个数。
接下来一行 n 个非负整数，第 i 个表示 a_i。
接下来 n-1 行，每行两个正整数 x,y，表示 x,y 在树上有一条边相连。
接下来 m 行，每行三个非负整数 x,u,v，表示一次事件。

数据保证：1\le n,m\le 2\times 10^5，0\le x,a_i\le 10^9。

输出描述:

输出共 m 行。第 i 行输出一个非负整数，表示第 i 个事件结束的记忆值。
示例1

输入

复制 
5 4
2 3 5 2 1
1 2
1 3
2 4
2 5
1 3 2
4 4 5
0 1 5
3 3 3

输出

复制 
11
4
0
6

说明

在样例中，小 L 的树如下图所示：

括号里的是这个点的点权。
以第 1 个事件为例，其中 x=1,u=3,v=2。小 L 在 3 号节点时记忆值变为 1\ \text{xor}\ 5=4，走过一条边后记忆值变为 4+1=5，在 1 号节点时记忆值变为 5\ \text{xor}\ 2=7，走过一条边后记忆值变为 7+1=8，在 2 号节点时记忆值变为 8\ \text{xor}\ 3=11，所以答案是 11。