最近,一棵树从天而降砸在了鲍勃的头上。该树有 $$$n$$$ 个节点。树的每个节点 $$$u$$$ 上都写有一个整数 $$$a_u$$$。但这棵树没有固定的根,因为它是从天上掉下来的。
Bob 目前正在研究这棵树。为了增加一些变化,爱丽丝提出了一个游戏。首先,Bob 选择某个节点 $$$r$$$ 作为树的根。之后,Alice 选择一个节点 $$$v$$$ 并告诉他。然后 Bob 可以从 $$$v$$$ 的子树中选取一个或多个节点。他的分数将是他所选择的节点上写入的所有值的按位异或。鲍勃必须找到给定 $$$r$$$ 和 $$$v$$$ 下他可以获得的最高分。
由于鲍勃不是一个善于解决问题的人,他要求你帮助他找到答案。你能帮助他吗?您需要为同一棵树找到 $$$r$$$ 和 $$$v$$$ 的多种组合的答案。
回想一下,树是一个没有循环的连通无向图。节点 $$$u$$$ 的子树是所有节点 $$$y$$$ 的集合,使得从 $$$y$$$ 到根的简单路径经过 $$$u$$$。请注意,$$$u$$$ 位于$$$u$$$ 的子树中。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 2 \cdot 10^5$$$) — 树的节点数。
下一行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) - 写入节点上的值。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\leq u, v\leq n$$$; $$$u\neq v$$$),表示节点 $$$u$$$ 和节点 $$$v$$$ 之间有一条无向边。保证给定的边形成一棵树。
下一行包含一个整数 $$$q$$$ ($$$1\leq q\leq 2 \cdot 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行包含两个整数 $$$r$$$ 和 $$$v$$$ ($$$1\leq r, v\leq n$$$) - Bob 定义的根节点和 Alice 选择的节点。
保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在每个查询中打印一行,其中包含一个整数,表示 Bob 可以获得的最大分数。
示例
输入 #1
3 6 12 12 8 25 6 1 1 5 1 2 2 6 2 3 2 4 3 4 2 3 5 1 2 2 3 8 1 2 4 2 2 2 1 1 2 1 1 3 3 8 7 1 2 2 3 2 2 2 2 1
输出 #1
15 6 29 11 3 8 11 15 3
注意
在下面的每张图中,绿色节点是 Bob 选择的节点,红色节点是 Alice 选择的节点。节点的值放置在节点旁边的蓝色框中。
考虑第一个例子。在第一个查询中,如果我们将根节点 $$$4$$$ 放在树的顶部,则树如下图所示:
第一个查询中根节点为 $$$4$$$ 的树。
在第二个查询中,如果根节点 $$$3$$$ 位于树的顶部,则树如下图所示:
第二个查询中根节点为 $$$3$$$ 的树。
在第三个查询中,如果根节点 $$$1$$$ 位于树的顶部,则树如下所示:
第三个查询中根节点为 $$$1$$$ 的树。