

AntsTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 327680/327680 K (Java/Others)Total Submission(s): 1577 Accepted Submission(s): 400 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 n1 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 kth 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 n1 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 kth ant. The input ends with n = 0. (1 <= n, m <= 100000, 1 <= x, y <= n, 0 <= z <= 10^{18}, 1 <= k <= 200000) Output For each query, output the answer. If such path does not exist, just output 1. Sample Input
Sample Output
Hint In the first test case, the first ant may crawl from node 2 to node 3, and the second ant may crawl from node 3 to node 2, and the 5th ant may crawl from node 1 to node 3. The distance of the 5th ant can be calculated by 2 xor 3 = 1. Source  
