给定一棵 $n$ 个节点的无根，有边权的树，每个点有个编号，编号为一个 $1 \sim n$ 的排列。

共 $m$ 组询问，每次询问给出 $l,r$，求所有点编号的二元组 $(i,j)$ 满足 $l \le i < j \le r$ 在树上的距离的和，两个点的距离定义为连接其的简单路径上的所有边的边权和。

输入格式

第一行两个空格隔开的数 $n$ $m$。

之后 $n-1$ 行，每行三个空格隔开的数 $u$ $v$ $d$ 表示一条 $u$ 和 $v$ 之间边权为 $d$ 的边。

之后 $m$ 行，每行两个空格隔开的数 $l$ $r$ 表示一次询问。

输出格式

共 $m$ 行，表示每个询问对应的答案，答案对 $2^{32}$ 取模。

样例数据

样例输入

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

样例输出

19
26
18
28
44
0

子任务

Idea：nzhtl1477，Solution：nzhtl1477，Code：zx2003，Data：nzhtl1477

对于 $100\%$ 的数据，$1\le n,m,d\le 2\cdot 10^5$，所有数值均为整数。