该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

【cy 篇 第二回】

拿到试卷后，cy 和 wjq 看到了最后一题——追及问题。

cy 和 wjq 的内心：“这题目不是 JC 昨天开玩笑给我们的 JC 密卷里面的原题吗！！！啊啊啊啊啊我没把它当回事没做啊！！！”

cy 和 wjq 看到题目中那复杂至极的数量关系，内心不停咒骂着出题人不能让他们过个好年，同时后悔自己没有做那套密卷……

出了考场后，他们出了一道 OI 题……

“要好好感谢下 JC！”

题目描述

wjq手上有一棵 \(n\) 个节点的树。这棵树的每一个节点有一个值。

现在wjq有 \(q\) 个询问，每次询问都要你回答节点 \(u\) 到节点 \(v\) 路径上的所有节点值的异或和。

输入格式

第一行，两个数 \(n,q\) 表示节点的个数以及询问数。

第二行，输入 \(n\) 个数，表示每个节点的权值 \(a_i\)。

接下来 \(n-1\) 行，每行两个数 \(u,v\)，表示这棵树有一条从 \(u\) 到 \(v\) 的边。

接下来 \(q\) 行，每行两个数 \(u,v\)，表示询问的起点和终点。

输出格式

对于每一个询问，输出一行，表示从 \(u\) 到 \(v\) 的路径上所有节点的异或和。

样例

输入#1

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

输出#1

7
6
6

数据范围

对于 \(20\%\) 的数据，满足 \(n,q \le 10\)。

对于 \(40\%\) 的数据，满足 \(n,q \le 1000\)。

对于 \(80\%\) 的数据，满足 \(n,q\le 10^5,a_i\le 2^{30}\)。

对于 \(100\%\) 的数据，满足 \(n\le 5\times 10^5,q\le 10^7,a_i\le 2^{30}\)，且树是随机生成的。

输入量可能很大，所以请使用较快的读入方式。