Tree XOR Queries

The xor operation is often referred to as non-carry addition. In everyday life, it is used in many scenarios. For example, if we represent a question's answer as $1$ for Yes and $0$ for No, then the expression:

\( (A\text{ is male}) \oplus (B\text{ is male}) \)

can determine whether $A$ and $B$ can be a couple.

Now, consider a more complex scenario. You are given a tree with $N$ nodes. Each edge in the tree carries an integer weight. The tree has exactly $N-1$ edges connecting the nodes. You are then given $M$ queries. For each query, you are provided with two nodes, and you need to calculate the bitwise xor (\( \oplus \)) of the weights of all the edges on the unique path connecting the two nodes.

Recall that for any two nodes \(u\) and \(v\), if we precompute the xor from a fixed root (say node $1$) to every other node as \( prefix[u] \) and \( prefix[v] \), then the xor on the path from \(u\) to \(v\) is given by

\[ \text{answer} = prefix[u] \oplus prefix[v] \]

inputFormat

The first line contains two integers $N$ and $M$, the number of nodes in the tree and the number of queries respectively.

The next $N-1$ lines each contain three integers $u$, $v$, and $w$, meaning there is an edge between node $u$ and node $v$ with weight $w$.

The following $M$ lines each contain two integers $u$ and $v$, representing a query for the xor of the edge weights on the path between node $u$ and node $v$.

It is guaranteed that the given graph is a tree (i.e. it is connected and has no cycles).

outputFormat

For each query, output a single integer — the xor of the weights on the path between the two given nodes.

sample

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

1
3