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

题目描述

圆滑博士最近在研究一棵神秘的树，这棵树有 $n$ 个节点，每个节点都有一个独特的权值。博士对这棵树非常感兴趣，他决定对两个节点之间路径上的权值进行研究。为了更好地理解这棵树的结构，他提出了以下问题。

给定一棵有 $n$ 个 节点的树，每个节点都有一个权值。树上的边连接了不同的节点，使得任意两个节点之间有且仅有一条路径。现在，圆滑博士想要你回答 $q$ 次询问，每次询问给出两个节点 $u$ 和 $v$ ，你需要计算这两个节点之间的路径上所有节点的权值的异或和。

输入格式

第一行包含一个整数 $n$ 表示树的节点数。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个节点的权值 $a_i(0\leq a_i \leq 10^9)$。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

接下来一行包含一个整数 $q$，表示询问的次数。

接下来 $q$ 行，每行包含两个整数 $u$ 和 $v$，表示你需要计算节点 $u$ 和节点 $v$ 之间的路径上所有节点的权值的异或和。

输出格式

输出 $q$ 行，每行一个整数，表示对应的路径上所有节点的权值的异或和。

样例

10
393805377 500929540 35233222 627072783 476414715 438246339 320220072 318131452 368521818 621259607
9 6
5 1
6 7
8 10
3 7
2 5
8 4
3 10
6 2
10
9 7
9 1
7 4
10 9
5 9
4 3
8 7
2 8
4 5
10 2

486408753
422494503
60690122
1004549280
240533350
277357922
654201285
557506050
406782966
869044990

数据范围

对于 $40\%$ 的数据，满足$n \leq 1000, q \leq 1000$；

对于 $100\%$ 的数据，满足$n \leq 2\times 10^5, q \leq 2 \times 10^5$。