{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e 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. \u003cbr\u003e 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.\u003cbr\u003e Note that the starting node and the ending node cannot be the same for an ant.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" The input consists of several test case.\u003cbr\u003e For each test case, the first line contain an integer n denoting the number of nodes.\u003cbr\u003e 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.\u003cbr\u003e The next line contain a integer m denoting the number of queries.\u003cbr\u003e In the next m lines, each line contains an integer k denoting that you need to calculate the distance of the k-th ant.\u003cbr\u003e The input ends with n \u003d 0.\u003cbr\u003e (1 \u0026lt;\u003d n, m \u0026lt;\u003d 100000, 1 \u0026lt;\u003d x, y \u0026lt;\u003d n, 0 \u0026lt;\u003d z \u0026lt;\u003d 10\u003csup\u003e18\u003c/sup\u003e, 1 \u0026lt;\u003d k \u0026lt;\u003d 200000)"}},{"title":"Output","value":{"format":"HTML","content":" For each query, output the answer. If such path does not exist, just output -1.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1 2 2\r\n3 2 3\r\n3\r\n1\r\n2\r\n5\r\n5\r\n1 3 7\r\n2 1 3\r\n4 3 6\r\n5 3 1\r\n3\r\n1\r\n8\r\n1000\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3\r\n1\r\n7\r\n6\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e 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 5-th ant may crawl from node 1 to node 3.\u003cbr\u003e The distance of the 5-th ant can be calculated by 2 xor 3 \u003d 1.\u003cbr\u003e"}}]}