Dis

题目描述

给出 $n$ 个点的一棵树，每个点有各自的点权，多次询问两个点简单路径所构成点集的异或和。

输入格式

第一行两个数字 $n$ 和 $m$ , $n$ 表示点数，$m$ 表示询问次数 。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示每个点的点权。

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

再接下来 $m$ 行，每行两个整数 $u,v$ ，表示询问点 $u$ 到点 $v$ 的简单路径所构成点集的异或和。

输出格式

输出 $m$ 行，对于每个询问，输出一行。

样例输入

7 3
0 1 2 3 4 5 6
1 2
1 3
2 4
2 5
3 6
3 7
4 6
4 7
5 6

样例输出

5
6
2

数据范围

所有数据保证 $1\leq n,m \leq 200000, 1 \leq a_i \leq 10^6$。