XOR Distance Queries on a Tree

Given an unrooted tree with n nodes numbered from 1 to n and non-negative integer weights on its edges, we define for every two nodes x and y the distance between them as the XOR sum of edge weights along the unique simple path connecting them. Formally, for any pair (x, y),

$$\operatorname{dis}(x, y) = \bigoplus_{e \in P(x,y)} w(e), $$

where \( \oplus \) denotes the bitwise XOR operation and \( P(x,y) \) is the set of edges on the unique simple path connecting x and y.

For any given nodes x and y, the value of a node i is defined as:

$$\operatorname{val}_{x,y}(i) = \operatorname{dis}(x,i) \oplus \operatorname{dis}(y,i). $$

You are then given q queries, each query consists of four integers x, y, l, r. For each query, compute:

$$\bigoplus_{i=l}^{r} \operatorname{val}_{x,y}(i),$$

where \( \oplus \) is the bitwise XOR. Note that due to the properties of XOR on trees, it can be shown that for any node i, \( \operatorname{val}_{x,y}(i) = \operatorname{dis}(x,y) \).

Thus the answer for a query becomes the XOR of the constant value \( \operatorname{dis}(x,y) \) taken over \( (r-l+1) \) times. In other words, if \( (r-l+1) \) is odd the answer is \( \operatorname{dis}(x,y) \) and if it is even the answer is 0.

inputFormat

The first line contains two integers n and q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵), representing the number of nodes and the number of queries.

The next n-1 lines each contain three integers u, v, and w (0 ≤ w ≤ 10⁹), indicating that there is an edge between nodes u and v with weight w.

The following q lines each contain four integers x, y, l, and r (1 ≤ x, y, l, r ≤ n and l ≤ r), representing one query.

outputFormat

For each query, output a single integer — the result of the XOR of \( \operatorname{val}_{x,y}(i) \) for all i from l to r.

sample

5 3
1 2 1
2 3 2
2 4 3
1 5 4
1 2 1 5
3 4 2 4
2 5 1 2

1
1
0

</p>