shik swallows and spits out. ber♂yu and Dide are entangled. The primes in the sky have not yet descended.

You stand at one of the foci of an ellipse, and the great Neet asks you a question.

Neet's question is as follows: first, you are given a tree with $n$ nodes, labeled $1 \sim n$, where each node has a weight $v_i$.

Then, Neet will ask $Q$ queries. Each query consists of two nodes $x, y$ on the tree and an integer $m$.

You need to return the maximum value obtained by selecting $m$ nodes on the simple path between these two nodes and performing a bitwise AND operation on their weights.

In particular, if there are fewer than $m$ nodes on the path, you must return $0$.

Because of shik, Neet's queries are forced to be online.

Input

The first line contains a single integer $n$, representing the number of nodes.

The next $n-1$ lines each contain two space-separated integers $x, y$, representing an edge between nodes $x$ and $y$.

The next line contains $n$ non-negative integers $v_i$, where the $i$-th integer represents the weight of the $i$-th node.

The next line contains a single integer $Q$, representing the number of queries.

The next $Q$ lines each contain three integers $x, y, m$. Because the queries are forced to be online, you need to decrypt the actual $x, y$. Let $lastans$ be the answer to the previous query (for the first query, $lastans$ is considered $0$). The actual $x', y'$ can be obtained as follows:

$x'=((x \oplus lastans) \bmod n)+1$, $y'=((y \oplus lastans) \bmod n)+1$, where $\oplus$ denotes bitwise XOR.

Output

$Q$ lines, each containing a non-negative integer representing your answer.

Examples

Input 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

Output 1

0
18
0

Note

In this dataset, the tree is a chain.

Decrypting the three queries gives $(x, y)$ as $(5, 5)$, $(4, 2)$, and $(5, 3)$.

For the first query, there are not enough nodes on the path, so the answer is $0$.

For the second query, the path passes through nodes $1, 2, 3, 4$. By selecting $1$ and $3$, we get $274 \operatorname{and} 2066 = 18$, which is the maximum.

For the third query, the path passes through $3, 4, 5$. It is easy to verify that the answer for any selection of three nodes is $0$.

Input 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

Output 2

2
2
0

Note

This is a random tree dataset. Decrypting gives $(7, 6)$, $(8, 1)$, and $(2, 4)$.

Constraints

| :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Subtask | Score | $n \leqslant$ | $m \leqslant$ | $Q \leqslant$ | $V \leqslant$ | Special Property | | $1$ | $5$ | $10^3$ | $3$ | $1$ | | Tree is a chain | | $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$ | | Tree is randomly generated | | $8$ | $35$ | | | | | |

Here $V$ represents the range of weights. If not specified in the table (i.e., blank), then $n \leqslant 10^6$, $m$ is randomly generated in $[2, 10]$, $Q \leqslant 10^5$, $0 \leqslant v_i \leqslant 2^{62}-1$, and the tree is a general tree.

The tree being generated in a random way means that for the $i$-th node, $2 \leqslant i \leqslant n$, node $i$ is connected to a node chosen uniformly at random from $[1, i-1]$.

For the $x, y$ in the queries (before decryption), it is guaranteed that $1 \leqslant x, y \leqslant n$.

Note

The input size is relatively large; please use efficient I/O methods.

keep your determinant!