题目描述

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$，其中 $⊕$ 代表按位异或。

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

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

数据范围与提示

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