题目描述

给定一棵 $n$ 个点的无根树，边有边权。

令 $E(x,y)$ 表示树上 $x,y$ 之间的简单路径上的所有边的集合，特别地，当 $x=y$ 时，$E(x,y) = \varnothing$。

你需要 实时 回答 $q$ 个询问，每个询问给定 $p,l,r$，请你求出集合 $\bigcap_{i=l}^r E(p,i)$ 中所有边的边权和，即 $E(p, l\dots r)$ 的交所包含的边的边权和。

通俗的讲，你需要求出 $p$ 到 $[l,r]$ 内每一个点的简单路径的公共部分长度。

输入格式

第一行两个整数 $n,q$，表示树的结点数和询问数。

接下来 $n-1$ 行，每行三个整数 $x,y,w$，表示 $x$ 与 $y$ 之间有一条权值为 $w$ 的边。

接下来 $q$ 行，每行三个整数 $p_0,l_0,r_0$。第 $i$ 个询问的 $p,l,r$ 分别为 $p_0,l_0,r_0$ 异或上 $lastans$ 的值，其中 $lastans$ 是上次询问的答案，初始时为 $0$。

输出格式

对于每个询问，一行一个整数，表示答案。

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

提示

【样例 1 说明】

样例中的树如图所示：

下面解释中的询问参数均为异或 $lastans$ 之后得到的真实值。

对于第一个询问，$p=2$，$l=3$，$r=5$，$\bigcap_{i=3}^5 E(2,i)$ 为边 $(2,3)$，长度为 $3$。

对于第二个询问，$p=1$，$l=2$，$r=4$，$\bigcap_{i=2}^4 E(1,i)$ 为边 $(1,3)$，长度为 $2$；

对于第三个询问，$p=2$，$l=5$，$r=5$，$\bigcap_{i=5}^5 E(2,i)$ 为边集 $\{(2,3),(3,1),(1,5)\}$，长度为 $6$；

对于第四个询问，$p=3$，$l=3$，$r=4$，$\bigcap_{i=3}^4 E(3,i)=\varnothing$，长度为 $0$。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，$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$。