Given is a tree with N weighted vertices and N-1 weighted edges. The i-th vertex has a weight of A_{i}. The i-th edge has a weight of W_{i} and connects vertices u_{i} and v_{i}.

Let $\operatorname{dist}(x,y)$ be the sum of weights of the edges in the unique [simple path] connecting vertices x and y.

Let $\operatorname{V}(x,y)$ be the set of vertices appearing in the unique simple path connecting vertices x and y (including x and y).

You are asked Q queries. In the i-th query, you are given two integers x_{i} and y_{i} and you need to compute:

$\sum\limits_{k\in$ $\operatorname{V}(x_{i},y_{i})}(\operatorname{dist}(x_{i},k)-\operatorname{dist}(k,y_{i}))\cdot A_{k}$

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line contains two integers N and Q.
• The second line contains $N integers A_{1},A_{2},\dots,A_{N}$.
• Each of the next N-1 lines contains three integers u_{i}, v_{i} and W_{i}.
• Each of the next Q lines contains two integers x_{i} and y_{i}.

------ Output Format ------

For each query, print the answer to it on a new line.

------ Constraints ------

$1≤T≤10^{3}$
$2 ≤N ≤2\cdot10^{5}$
$1 ≤Q ≤2\cdot10^{5}$
$1 ≤A_{i},W_{i} ≤10^{4}$
$1≤u_{i},v_{i},x_{i},y_{i}≤N$
$x_{i}\ne y_{i}$
$u_{i}\ne v_{i}$
- The sum of $N$ across all test cases does not exceed $2\cdot 10^{5}$.
- The sum of $Q$ across all test cases does not exceed $2\cdot 10^{5}$.

------ subtasks ------

Subtask #1 (20 points): $u_{i}=i,v_{i}=i+1$
Subtask #2 (80 points): Original constraints

----- Sample Input 1 ------
2
5 2
5 3 3 1 2
1 2 2
2 3 1
2 4 1
1 5 2
4 5
5 4
10 5
3 6 9 2 3 8 3 7 9 7
1 2 4
1 3 6
1 4 8
4 5 9
1 6 2
5 7 3
3 8 7
3 9 2
7 10 9
9 2
2 1
8 5
3 2
3 10
----- Sample Output 1 ------
1
-1
-96
-12
-252
-24
-69
----- explanation 1 ------
Test Case $1$:
- For the first query, $\operatorname{V}(4,5)=\{4,2,1,5\}$. The answer is $1\cdot(0-5)+3\cdot(1-4)+5\cdot(3-2)+2\cdot(5-0)=1$
- For the second query, $\operatorname{V}(5,4)=\{5,1,2,4\}$. The answer is $2\cdot(0-5)+5\cdot(2-3)+3\cdot(4-1)+1\cdot(5-0)=-1$

见题面

见题面