Alice and Bob

As you know, Alice and Bob always play game together, and today they get a tree.

The tree consists of $n$ vertices, and vertex $1$ is the root of this tree.

There is a number $w[i]$ written on the ith vectex. Alice and Bob want to play a game on a subtree of this tree. (Note that there are only $n$ subtrees, since the tree is rooted.)

Firstly Alice will choose a vertex in this subtree, and Bob must to choose a different vertex in this subtree. (So, Bob knows which vertex Alice chosen.)

At last they will get a result number equals the XOR sum of the number written on the two vertices which they chosen.

But the problem is that Alice wants the result number to be as maximal as possible while Bob wants the result number to be as minimal as possible, and of course they are clever enough.

Now we are interested in the result number, can you tell us?

In the first line there is an integer $T$, indicating the number of test cases.

For each test case:

The first line includes an integer $n$.

The second line includes $n$ integers $w[i]$, indicating the number written on the ith vertex.

For the next $n-1$ lines, each line includes two integers $u$ and $v$, which means an edge in the tree.

The next line includes an integer $m$, which means the number of our queries.

The next $m$ lines, each line includes an integer $u$, indicating Alice and Bob play game on the subtree rooted on the vertex $u$, and we want to know the result number.

$1 \leq n, m \leq 100000, 0 \leq w[i] \leq 100000$.

For each test case:

Output “Case #k:”(without quotes) one line first, where k means the case number count from 1.

Then output $m$ lines, each line must include the answer of the corresponding query. If Alice and Bob can’t choose two different vertices, output -1 instead.

1
3
1 2 3
1 2
2 3
3	
1
2
3

Case #1:
2
1
-1

UESTC

2016中国大学生程序设计竞赛 - 网络选拔赛