又一树上异或和
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一棵由 n 个节点构成的树，每一个点都有其对应的乐趣值 a_i。
\hspace{15pt}对于树上的任意一条路径（可以不是简单路径），记这条路径上所有点的乐趣值的异或和为这条路径的“总乐趣值”。注意，如果一个点多次经过，那么这个点的乐趣值要参与多次异或运算。
\hspace{15pt}XiaoT 想要从中制定旅行方案，于是他进行了 q 次询问，对于每次询问：
\hspace{15pt}选择起点 a 和终点 b，请你告诉他以点 a 为起点，点 b 为终点的所有路径中，能得到的最大“总乐趣值”是多少。这里的路径不一定是简单路径，同时也不一定要到达 a 点或 b 点后立刻停止。

输入描述:

\hspace{15pt}第一行输入两个正整数 n,q \left(1\le n \le 10^5;\ 1\le q\le 2\times 10^5\right) 代表树上的节点数量、询问次数。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left(0\le a_i\lt 2^{31}\right) 代表每个点的乐趣值。
\hspace{15pt}此后 n-1 行，第 i 行输入两个正整数 u_i,v_i \left(1\le u_i,v_i\le n\right) 代表树上的第 i 条边连接节点 u_i 和节点 v_i。
\hspace{15pt}此后 q 行，每行输入两个正整数 a,b \left(1\le a,b\le n\right) 代表一次询问。

输出描述:

\hspace{15pt}对于每一次询问，新起一行。输出一个整数，代表最大的“总乐趣值”。
示例1

输入

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

输出

复制 
3
3

说明

\hspace{15pt}在这个样例中，树的形状如下图所示。我们使用 \oplus 表示异或运算。
alt text\hspace{15pt}
    对于第一次查询，其中一种可行的路径是 2\to 1\to 2\to 1\to 3，答案计算为 a_2 \oplus a_1 \oplus a_2 \oplus a_1 \oplus a_3 = 3。
\hspace{15pt}对于第二次查询，其中一种可行的路径是 2\to 1\to 3\to 4\to 3\to 5 ，答案计算为 a_2 \oplus a_1 \oplus a_3 \oplus a_4 \oplus a_3 \oplus a_5 = 3。
示例2

输入

复制 
4 3
1 3 5 17
1 2
2 3
3 4
1 4
2 3
4 2

输出

复制 
22
22
23