Distance

Problem Description

You are given a tree with $n$ nodes, each edge of the tree has a weight, the nodes of the tree are numbered from $1$ to $n$. Let $\texttt {dist}(i,j)$ be the sum of edges' weight on the path between $i$ and $j$. You need to answer $m$ queries, each query is given $l,r$, you are asked to output the sum of all $\texttt {dist}(i,j)$, that satisfies $l \le i<j \le r$.

Input

The input contains several test cases, and the first line contains a single integer $T$, the number of test cases. For each test case: The first line contains two integers $n,m$. For the following $n-1$ lines, each line contains three integers $u,v,d$, which means that there is an edge between $u,v$, the weight of this edge is $d$. For the following $m$ lines, each line contains two integers $l,r$, which means that there is a query for $l,r$. $1 \le T \le 3$，$1\le n,m,d\le 2\cdot 10^5$, $l \le r$, all input are integers.

Output

For each test case, output $m$ lines representing the answer for the given $m$ queries. You need to output the answer module $2^{32}$.

Sample Input

3
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
6 6
2 1 3
3 1 2
4 3 1
5 1 1
6 3 3
2 4
2 4
1 1
1 6
1 4
1 1
6 6
6 5 2
1 6 3
4 1 1
3 5 2
2 4 3
5 5
1 3
1 1
3 4
4 5
1 1

Sample Output

19
26
18
28
44
0
12
12
0
58
20
0
0
22
0
8
6
0

Source

2020 Multi-University Training Contest 9