You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

山里有不动的树，山里还有灵活的狗，还有……

这是神里绫华，她很好看。

题目描述

给定一颗 $N$ 个节点的有根树，1号节点为根节点，点 $i$ 的权值为 $w_i$，有 $Q$ 次询问，每次询问给出三个数 $u,v,x$ ，树上从 $u$ 到 $v$ 的路径上的所有点的集合记为 $S$ 集合，求出

即分别求出从 $u$ 到 $v$ 的路径上的所有点和 $x$ 的最近公共祖先，之后把这些最近公共祖先的权值求和。

注：$lca(a,b)$ 表示 $a,b$ 的最近公共祖先。

输入

第一行一个正整数 $T$ 表示数据组数。

对于每组数据，第一行两个正整数 $N,Q(1 \leq N,Q \leq 10^5)$​ 分别表示节点的数量和询问数量。

接下来一行 $N$ 个正整数，第 $i$ 个正整数表示第 $i$ 个节点的权值 $w_i(-10^9 \leq w_i \leq 10^9)$ 。

接下来 $N-1$ 行，每行两个正整数 $u,v(1 \leq u,v \leq N)$ 表示树中存在一条连接 $u$ 和 $v$ 的边，保证给出的数据一定形成一棵树。

最后 $Q$ 行，每行三个正整数 $u,v,x(1 \leq u,v,x \leq N)$​ 表示一次询问。

保证 $N,Q$ 的和不超过 $10^5$。

输出

对于每组数据输出 Q 行，按顺序输出每次询问的结果 $\sum_{i \in S}{w_{lca(i,x)}}$

样例

1
9 4
8 4 3 6 3 6 10 5 2
1 2
2 3
2 4
2 5
3 6
3 7
4 8
8 9
1 1 1
1 2 5
6 8 7
6 8 5

8
12
18
20