有 $n$ 个节点，第 $x$ 个节点有点权 $a_x$，有两棵树分别独立地连接了这 $n$ 个点，两棵树点权是共用的。
你需要进行 $m$ 次操作，每次操作给定 $x, y, k$，进行以下两步：
- 将第一棵树上 $x, y$ 之间最短路径上所有节点的点权增加 $k$；
- 求第二棵树上 $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$
| 子任务编号 | $n, m \leq$ | 特殊性质 | 分值 |
|---|---|---|---|
| 1 | 3000 | 无 | 5 |
| 2 | $7 \times 10^4$ | 12 | |
| 3 | $1.2 \times 10^5$ | 13 | |
| 4 | $2 \times 10^5$ | A | 14 |
| 5 | B | 17 | |
| 6 | C | 19 | |
| 7 | 无 | 20 |
- 特殊性质 A：保证第二棵树在所有 $n$ 个节点的无根树中均匀随机生成。
- 特殊性质 B：保证两棵树均为均匀随机生成的链。
- 特殊性质 C：保证对于第一棵树，在以 $1$ 为根的情况下，每个节点的父亲编号小于自己，且每个子树内节点编号连续，对于第二棵树的第 $x$ 条边，连接节点 $x$ 和 $x+1$。