「TFOI R1」Tree Home

阳光开朗大男孩天才 Z 今天要向蕉太狼表白力！ 众所周知，蕉太狼是一个很可爱的女孩纸。 从前的天才 Z 总是担心因为自己表白失败而受到别人的嘲笑。但是今天，天才 Z 就要做出自己一生中最重要的一件事，那就是真诚地表白，无论后果如何。 出乎意料，蕉太狼其实也喜欢着天才 Z！ 天才 Z 开心得像个 0#。 但是没过多久，天才 Z 就被甩力，原因蕉太狼发现天才 Z 对自己的闺蜜有非分之想。 天才 Z 拿出了自己的树状家谱，问候起了自己的祖宗们。

有一个由 $n - 1$ 条**带权无向边**连接成的有 $n$ 个节点的树，每个节点都有它对应的**编号**以及**权值** $v_{i}$，整棵树的根节点为编号为 $1$ 的节点。 令 $f(a, b, c) = (a - b) \times \left[a^2 + b^2 + a \times b + 3 \times c \times (a + b + c)\right]$，其中 $a,b,c$ 可以为任意整数。同时用 $d_i$ 表示 $i$ 到根节点的每条边的**边权**之和。 现在天才 Z 要进行 $T$ 次询问，每次询问给定四个正整数 $l_{1},r_{1},l_{2},r_{2}$，你要从**编号**在区间 $[l_{1}, r_{1}]$ 和 $[l_{2}, r_{2}]$ 的点中各选择一个点 $p$ 和 $q$，当然你选择的两个点需要保证 $p \neq q$。用 $r$ 表示 $p$ 和 $q$ 的最近公共祖先，要使得 $|f(d_{p} - d_{r}, d_{q} - d_{r}, d_{r})| + |v_{p} - v_{q}|$ 的值最大，而你需要对每次询问输出这个最大值。

第一行输入两个正整数 $n$ 和 $T$，表示这棵树的节点个数以及询问次数。 第二行输入 $n$ 个整数，第 $i$ 个数表示编号为 $i$ 的节点的权值。 接下来 $n - 1$ 行，每行输入三个整数 $u,v,w$，表示节点 $u$ 到节点 $v$ 之间有一条边权为 $w$ 的无向边。 接下来 $T$ 行，每行输入四个整数 $l_{1},r_{1},l_{2},r_{2}$，表示一次询问（意义如题面所述）。

输出 $T$ 行，每行输出一个整数，表示每次询问的答案。

7 2
5 1 7 12 5 9 6
1 2 5
3 1 1
6 2 9
4 6 14
7 6 4
5 2 10
2 4 5 7
1 1 3 3

19211
3

#### 样例解释 对于第一次询问，我们在两个区间分别取 $4$ 号点和 $6$ 号点即可得出答案 $19211$。 对于第二次询问，两个区间都只能取一个节点，所以答案为 $3$。 #### 数据范围 **本题采用捆绑测试**。 - Subtask 1（5 points）：$1 \leqslant n, T \leqslant 10$。 - Subtask 2（10 points）：$1 \leqslant n, T \leqslant 100$。 - Subtask 3（30 points）：$1 \leqslant n, T \leqslant 3000$。 - Subtask 4（55 points）：无特殊限制。 对于所有数据，$1 \leqslant n, T \leqslant 2 \times 10^5$，$0 \leqslant |w| \leqslant 25$，$1 \leqslant v_{x} \leqslant 10^9$，$1 \leqslant l_{1} \leqslant r_{1} \leqslant n$，$1 \leqslant l_{2} \leqslant r_{2} \leqslant n$，保证树中最大深度不超过 $100$。 **注意：两个区间 $[l_{1}, r_{1}]$ 和 $[l_{2}, r_{2}]$ 可能有重合部分。**