题目背景
shik 吞进去又吐出来。ber♂宇和抵德纠缠个不清。天空中的素数还没有降下。
你站在椭圆的一♂焦,伟大尼特向你发问。
题目描述
尼特问的这个问题是这样的，首先你有一棵 $n$ 个节点的树，节点标号 $1∼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⊕lastans)\bmod n)+1$，$y'=((y⊕lastans)\bmod n)+1$，其中 $⊕$ 代表按位异或。
输出格式
$Q$ 行,每行一个非负整数代表你的答案
样例数据
样例输入一
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 \operatorname{and} 2066=18$ 最大。
对于第三个询问,其经过 $3,4,5$，容易验算选取三对的答案都是 $0$。
样例输入二
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$ | $5$ | $10^5$ | ||||
| $3$ | $10$ | $10^5$ | $2$ | $1$ | $65535$ | |
| $4$ | $5$ | $10^6$ | $ $ | $ $ | ||
| $5$ | $10$ | $10^5$ | $10^4$ | |||
| $6$ | $15$ | $ $ | ||||
| $7$ | $15$ | $10^6$ | $10^5$ | 树按照某种方式随机生成 | ||
| $8$ | $35$ | $ $ |
其中 $V$ 表示权值范围，如表格中无特殊说明（即空白），则有 $n⩽10^6$，$m$ 在 $[2,10]$ 之间随机生成，$Q⩽10^5$，$0⩽v_i⩽2^{62}−1$，树为普通的树。
树按照某种随机方式生成的意思是，对于第 $i$ 个点，$2⩽i⩽n$，有 $i$ 向 $[1,i−1]$ 中均匀随机的一个数连边。
对于题目中询问的 $x,y$（加密前），保证有 $1⩽x,y⩽n$。
提示
读入量偏大,请使用比较高效的读入方式
keep your determinant!