有 $n$ 个节点，第 $x$ 个节点有点权 $a_x$，有两棵树分别独立地连接了这 $n$ 个点，两棵树点权是共用的。

你需要进行 $m$ 次操作，每次操作给定 $x, y, k$，进行以下两步：

1. 将第一棵树上 $x, y$ 之间最短路径上所有节点的点权增加 $k$；
2. 求第二棵树上 $x, y$ 之间最短路径上的点权和对 $2^{64}$ 取模的结果。

输入格式

第一行两个数 $n, m$，表示节点数和操作数。

第二行 $n$ 个数，第 $x$ 个数表示 $a_x$，即节点 $x$ 的初始点权。

接下来 $n-1$ 行，每行两个数 $x, y$，表示第一棵树上节点 $x$ 和节点 $y$ 之间有一条边。

接下来 $n-1$ 行，每行两个数 $x, y$，表示第二棵树上节点 $x$ 和节点 $y$ 之间有一条边。

接下来 $m$ 行，每行三个数 $x, y, k$，表示一次操作。

输出格式

输出 $m$ 行，每行一个数，表示每次操作的答案。

样例输入 1

3 2
1 10 100
2 3
3 1
1 3
3 2
2 3 1000
1 1 10000

样例输出 1

2110
10001

样例输入 2

5 7
0 3 2 6 4
1 2
2 4
1 5
5 3
3 4
4 2
2 5
5 1
5 3 0
3 2 5
4 4 4
4 4 3
5 2 0
3 4 3
5 5 6

样例输出 2

15
21
10
13
17
26
18

数据范围

• 对于所有数据满足 $1 \leq n, m \leq 2 \times 10^5$
• $0 \leq a_i, k < 2^{64}$
• $1 \leq x, y \leq n$

• 特殊性质 A：保证第二棵树在所有 $n$ 个节点的无根树中均匀随机生成。
• 特殊性质 B：保证两棵树均为均匀随机生成的链。
• 特殊性质 C：保证对于第一棵树，在以 $1$ 为根的情况下，每个节点的父亲编号小于自己，且每个子树内节点编号连续，对于第二棵树的第 $x$ 条边，连接节点 $x$ 和 $x+1$。