Problem Description
There are some apple trees in a farm. An apple tree can be described as a connected graph which has n nodes and n-1 edges. The apples are the nodes and the branches are the edges. Every edge is assigned a value denoting the length of the branch.
Now in the farm come a lot of ants, which are going to enjoy the delicious apples. The ants climb the tree one by one. Every ant would choose a node as the starting node and another node as the ending node, then it would crawl alone the unique path from the starting node to the ending node. The distance between two nodes is defined as the XOR sum of lengths of all the edges in the unique path between them. Every ant wants to crawl along such a path which the distance is as large as possible. But two ants cannot crawl from the same starting node to the same ending node. You should calculate the distance which the k-th ant crawled.
Note that the starting node and the ending node cannot be the same for an ant.
Input
The input consists of several test case.
For each test case, the first line contain an integer n denoting the number of nodes.
The next n-1 lines each contains three integers x,y,z, denoting that there exists an edge between node x and node y and its length is z. The nodes are numbered from 1 to n.
The next line contain a integer m denoting the number of queries.
In the next m lines, each line contains an integer k denoting that you need to calculate the distance of the k-th ant.
The input ends with n = 0.
(1 <= n, m <= 100000, 1 <= x, y <= n, 0 <= z <= 1018, 1 <= k <= 200000)
Output
For each query, output the answer. If such path does not exist, just output -1.
Sample Input
3
1 2 2
3 2 3
3
1
2
5
5
1 3 7
2 1 3
4 3 6
5 3 1
3
1
8
1000
0
Sample Output
3
3
1
7
6
-1
