Description

Given an undirected tree with $n$ nodes, where each edge has a weight.

Let $E(x,y)$ denote the set of all edges on the simple path between $x$ and $y$ in the tree. In particular, when $x=y$, $E(x,y)=\varnothing$.

You need to answer $q$ queries online. Each query gives $p,l,r$. Please compute the sum of edge weights of all edges in the set $\bigcap_{i=l}^r E(p,i)$, i.e. the sum of edge weights contained in the intersection of $E(p, l\dots r)$.

In simple terms, you need to find the length of the common part of the simple paths from $p$ to every node in $[l,r]$.

Input Format

The first line contains two integers $n,q$, representing the number of nodes in the tree and the number of queries.

The next $n-1$ lines each contain three integers $x,y,w$, indicating that there is an edge between $x$ and $y$ with weight $w$.

The next $q$ lines each contain three integers $p_0,l_0,r_0$. For the $i$-th query, the actual $p,l,r$ are obtained by XOR-ing $p_0,l_0,r_0$ with $lastans$, respectively, where $lastans$ is the answer to the previous query and is initially $0$.

Output Format

For each query, output one integer per line, representing the answer.

5 4
3 1 2
1 5 1
2 3 3
3 4 4
2 3 5
2 1 7
0 7 7
5 5 2

3
2
6
0

10 10
2 1 9907
3 2 8329
4 2 8402
5 4 3636
6 4 8747
7 4 3080
8 6 780
9 6 5414
10 9 3545
2 10 10
26107 26106 26101
4 9 10
14171 14166 14169
8958 8949 8949
36008 36014 36013
11485 11485 11472
3 9 9
30888 30894 30895
8404 8404 8411

26108
0
14161
8959
36015
11482
0
30892
8402
0

Hint

[Sample 1 Explanation]

The tree in the sample is shown in the figure:

In the explanations below, all query parameters are the real values after XOR with $lastans$.

For the first query, $p=2$, $l=3$, $r=5$, and $\bigcap_{i=3}^5 E(2,i)$ is the edge $(2,3)$, with total length $3$.

For the second query, $p=1$, $l=2$, $r=4$, and $\bigcap_{i=2}^4 E(1,i)$ is the edge $(1,3)$, with total length $2$.

For the third query, $p=2$, $l=5$, $r=5$, and $\bigcap_{i=5}^5 E(2,i)$ is the edge set $\{(2,3),(3,1),(1,5)\}$, with total length $6$.

For the fourth query, $p=3$, $l=3$, $r=4$, $\bigcap_{i=3}^4 E(3,i)=\varnothing$, and the total length is $0$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the data, $1\leq n,q\leq 2\times 10^5$, $1\leq x,y,p\leq n$, $1\leq l\leq r\leq n$, and $1\leq w\leq 10^4$.

Translated by ChatGPT 5