Background

The sunny and cheerful genius boy Z is going to confess his love to Jiao Tailang today!

As everyone knows, Jiao Tailang is a very cute girl. In the past, genius Z always worried that he would be laughed at if his confession failed. But today, genius Z is going to do the most important thing in his life: confess sincerely, no matter what the result is.

Unexpectedly, Jiao Tailang also likes genius Z!

Genius Z is as happy as a 0#.

But not long after that, genius Z got dumped. The reason is that Jiao Tailang found out that genius Z had improper thoughts about her best friend.

Genius Z pulled out his tree-shaped family tree and started greeting his ancestors.

Problem Description

There is a tree with $n$ nodes connected by $n - 1$ weighted undirected edges. Each node has its corresponding index and weight $v_{i}$. The root of the whole tree is the node with index $1$.

Let $f(a, b, c) = (a - b) \times \left[a^2 + b^2 + a \times b + 3 \times c \times (a + b + c)\right]$, where $a, b, c$ can be any integers. Also, let $d_i$ denote the sum of the edge weights on the path from node $i$ to the root.

Now genius Z will make $T$ queries. In each query, four positive integers $l_{1}, r_{1}, l_{2}, r_{2}$ are given. You need to choose one node $p$ from the nodes whose indices are in the interval $[l_{1}, r_{1}]$, and choose one node $q$ from the nodes whose indices are in the interval $[l_{2}, r_{2}]$. Of course, the two chosen nodes must satisfy $p \neq q$. Let $r$ be the lowest common ancestor of $p$ and $q$. You need to maximize the value of $|f(d_{p} - d_{r}, d_{q} - d_{r}, d_{r})| + |v_{p} - v_{q}|$, and output this maximum value for each query.

Input Format

The first line contains two positive integers $n$ and $T$, representing the number of nodes in the tree and the number of queries.

The second line contains $n$ integers. The $i$-th number is the weight of the node with index $i$.

The next $n - 1$ lines each contain three integers $u, v, w$, indicating that there is an undirected edge with weight $w$ between nodes $u$ and $v$.

The next $T$ lines each contain four integers $l_{1}, r_{1}, l_{2}, r_{2}$, indicating one query (with the meaning described above).

Output Format

Output $T$ lines. Each line contains one integer, representing the answer to each query.

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

Hint

Sample Explanation

For the first query, we can take node $4$ from the first interval and node $6$ from the second interval, obtaining the answer $19211$.

For the second query, each interval can only choose one node, so the answer is $3$.

Constraints

This problem uses bundled testdata.

• 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): no special restrictions.

For all data, $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$. It is guaranteed that the maximum depth of the tree does not exceed $100$.

Note: the two intervals $[l_{1}, r_{1}]$ and $[l_{2}, r_{2}]$ may overlap.

Translated by ChatGPT 5