时间限制 $\texttt{3s}$

空间限制 $\texttt{512MB}$

题目背景

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)$

限制与约定

其中 $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!