G. 你的损失

时间限制：3 秒
内存限制：256 兆字节

给你一棵有 $n$ 个节点的树，节点编号为 $1$ 到 $n$，以及一个大小为 $n$ 的数组。第 $i$ 个节点的值为 $a_i$。有 $q$ 个查询。每个查询中，你会得到两个节点 $x$ 和 $y$。

考虑从节点 $x$ 到节点 $y$ 的路径。设该路径表示为 $x = p_0, p_1, p_2, \dots, p_r = y$，其中 $p_i$ 是路径上的节点。计算

其中 $\oplus$ 表示按位异或运算。

更正式地说，计算

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。每个测试用例包含若干组输入数据。

每组输入数据的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）——节点的数量。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 与节点 $v$ 之间有一条边。保证 $u \neq v$，且这些边构成一棵树。

再下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 5 \cdot 10^5$）——节点的值。

再下一行包含一个整数 $q$（$1 \le q \le 10^5$）——查询的数量。

接下来 $q$ 行描述查询。第 $i$ 个查询包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示路径的起点和终点。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$，所有测试用例的 $q$ 之和不超过 $10^5$。

输出

对于每个查询，输出一个整数——题目描述中所述的和。

示例

输入

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

输出

14
10
2