题目背景

shik 吞进去又吐出来。ber♂宇和抵德纠缠个不清。天空中的素数还没有降下。

你站在椭圆的一♂焦,伟大尼特向你发问。

题目描述

尼特问的这个问题是这样的，首先你有一棵 $n$ 个节点的树，节点标号 $1 \sim n$，树上每个节点都有一个权值 $v_i$。

然后尼特会询问 $Q$ 次，每次询问树上的两个节点 $x,y$，以及一个数 $m$。

然后你需要返回在这两个节点形成的简单路径上选取 $m$ 个节点,并将其权值按位与起来获得的值最大是多少。

特别的，如果这条路径上的节点不足 $m$ 个,你要返回 $0$。

由于 shik，尼特的询问强制在线。

输入格式

第一行单独的一个数 $n$，表示节点个数 $n$。

接下来 $n-1$ 行，每行有两个空格隔开的整数 $x,y$，表示节点 $x,y$ 之间有一条边。

再接下来单独一行 $n$ 个非负整数 $v_i$，表示每个节点的权值，其中第 $i$ 个非负整数 $v_i$ 表示第 $i$ 个节点的权值。

接下来一行单独的一个整数 $Q$，表示询问个数。

接下来 $Q$ 行，每行三个整数 $x,y,m$，由于强制在线，你需要解密得到真正的 $x,y$，不妨设上一次你输出的答案为 $lastans$（第一次询问 $lastans$ 视作 $0$），则真正的 $x',y'$ 可以使用以下方式获取：

$x' = ((x \oplus lastans) \bmod n) + 1$，$y' = ((y \oplus lastans) \bmod n) + 1$，其中 $\oplus$ 代表按位异或。

输出格式

$Q$ 行，每行一个非负整数代表你的答案。

样例 1

输入

5
1 2
3 1
4 3
5 4
274 5134 2066 17120 40972 
3
4 4 2
3 1 2
1 4 2

输出

0
18
0

在这组数据中树是一条链。

解密得到三组询问的 $(x,y)$ 分别是 $(5,5)$，$(4,2)$ 和 $(5,3)$。

其中第一个询问路径上不满两个数,从而为 $0$。

对于第二个询问，其经过 $1,2,3,4$ 节点,通过选取 $1,3$，我们得到 $274 \ \text{and} \ 2066 = 18$ 最大。

对于第三个询问,其经过 $3,4,5$，容易验算选取三对的答案都是 $0$。

样例 2

输入

10
2 1
3 1
4 1
5 2
6 1
7 1
8 7
9 3
10 3
53290 0 388 0 70 2 9750 2114 186 0 
3
6 5 3
5 8 3
3 1 3

输出

2
2
0

这是随机树的数据，解密得到 $(7,6)$，$(8,1)$，$(2,4)$

数据范围与提示

子任务	分值	$n \leqslant$	$m \leqslant$	$Q \leqslant$	$V \leqslant$	特殊性质
1	5	$10^3$	3	1		树是一条链
2				$10^5$
3	10	$10^5$	2	1	65535
4	5	$10^6$
5	10	$10^5$		$10^4$
6	15
7		$10^6$		$10^5$		树按照某种方式随机生成
8	35

其中 $V$ 表示权值范围，如表格中无特殊说明（即空白），则有 $n \leqslant 10^6$，$m$ 在 $[2,10]$ 之间随机生成，$Q \leqslant 10^5$，$0 \leqslant v_i \leqslant 2^{62} - 1$，树为普通的树。

树按照某种随机方式生成的意思是，对于第 $i$ 个点，$2 \leqslant i \leqslant n$，有 $i$ 向 $[1,i-1]$ 中均匀随机的一个数连边。

对于题目中询问的 $x,y$（加密前），保证有 $1 \leqslant x,y \leqslant n$。

提示 读入量偏大,请使用比较高效的读入方式

keep your determinant!