Problem Description

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

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

You need to answer $q$ queries in real-time. Each query provides $p, l, r$, and you are asked to compute the sum of the weights of the edges in the set $\bigcap_{i=l}^r E(p,i)$, which is the intersection of the paths from $p$ to each node in the range $[l, r]$.

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

Input Format

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

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

The following $q$ lines each contain three integers $p_0, l_0, r_0$. The values of $p, l, r$ for the $i$-th query are obtained by XORing $p_0, l_0, r_0$ with $lastans$, where $lastans$ is the answer to the previous query, initialized to $0$.

Output Format

For each query, output a single integer on a new line, representing the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
2
6
0

Input Sample #2

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

Output Sample #2

26108
0
14161
8959
36015
11482
0
30892
8402
0

Notes

Sample 1 Explanation

The tree in the sample is illustrated as follows:

The parameters for the queries below are the actual values after XORing with $lastans$.

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

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

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

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

Data Range

This problem uses subtask testing.

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$, $1 \leq w \leq 10^4$.

见题面 Input 部分

见题面 Output 部分