Description

XOR is a special operation, often summarized as addition without carry.

In daily life, xor is also common. For example, for a yes/no question, yes is $1$ and no is $0$, then: (A is male) xor (B is male) = whether A and B can become a couple.

Now, we will handle a more complex case. You are given a tree with $N$ nodes. Each edge has a weight. There are $M$ queries. For each query, find the XOR of all edge weights along the path between two nodes.

Input Format

The first line contains an integer $N$, the number of nodes in the tree. The next $N - 1$ lines each contain three integers $u, v, w$, indicating there is an edge between $u$ and $v$ with weight $w$. The next line contains an integer $M$, the number of queries. Each of the next $M$ lines contains two integers $u, v$, asking for the XOR of the edge weights along the path between $u$ and $v$.

Output Format

Output $M$ lines, each with one integer, the XOR value.

5
1 4 9644
2 5 15004
3 1 14635
5 3 9684
3
2 4
5 4
1 1

975
14675
0

Hint

Constraints:

• For $40\%$ of the testdata, $1 \le N, M \le 3000$.
• For $100\%$ of the testdata, $1 \le N, M \le 100000$.
• Edge weights are within the int range.

Translated by ChatGPT 5