给您一棵树,其中包含 $$$n$$$ 节点,编号从 $$$1$$$ 到 $$$n$$$,以及大小为 $$$n$$$ 的数组。第 $$$i$$$ 个节点的值为 $$$a_{i}$$$。有 $$$q$$$ 查询。在每个查询中,您都会获得 2 个节点,编号为 $$$x$$$ 和 $$$y$$$。
考虑从编号为 $$$x$$$ 的节点到编号为 $$$y$$$ 的节点的路径。令路径由 $$$x = p_0, p_1, p_2, \ldots, p_r = y$$$ 表示,其中 $$$p_i$$$ 是中间节点。计算每个 $$$i$$$ 的 $$$a_{p_i}\oplus i$$$ 之和,使得 $$$0 \le i \le r$$$ 其中 $$$\oplus$$$ 是 XOR 运算符。
更正式地说,计算 $$$$$$\sum_{i =0}^{r} a_{p_i}\oplus i$$$$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。每个测试用例包含多组输入数据。
每组输入数据的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 节点数。
每组输入数据的接下来的$$$n-1$$$行包含$$$2$$$整数,$$$u$$$和$$$v$$$表示编号为$$$u$$$的节点和编号为$$$v$$$的节点之间的边。保证 $$$u \ne v$$$ 并且边形成一棵树。
每组输入数据的下一行包含 $$$n$$$ 整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^5$$$) — 节点的值。
下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行描述查询。第 $$$i$$$ 查询包含 $$$2$$$ 整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x,y \le n$$$) 表示路径的起始和结束节点。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$,所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$。
输出
对于每个查询,输出一个数字 - 问题陈述的总和。
示例
输入 #1
1 4 1 2 2 3 3 4 2 3 6 5 3 1 4 3 4 1 1
输出 #1
14 10 2