Maximizing Function Value on a Weighted Tree

You are given a tree of n nodes connected by n-1 undirected weighted edges. Each node i has an associated value v_i and a unique label from 1 to n. The tree is rooted at node 1.

For each node i, let d_i denote the sum of edge weights on the unique path from node i to the root.

Define the function \[ f(a,b,c) = (a - b)\times \Bigl(a^2 + b^2 + a \times b + 3 \times c \times (a+b+c)\Bigr), \] where a, b, and c can be any integers.

You are also given T queries. In each query, you are given four positive integers l₁, r₁, l₂, r₂. It is required to choose two distinct nodes p and q such that the labels of p and q fall within the intervals [l₁, r₁] and [l₂, r₂] respectively. Let r be the lowest common ancestor (LCA) of p and q. Your task is to maximize the expression \[ \left|f(d_{p}-d_{r},\,d_{q}-d_{r},\,d_{r})\right| + \left|v_{p}-v_{q}\right|. \] For each query, output the maximum value achievable.

inputFormat

The first line contains two integers n and T --- the number of nodes and the number of queries.

The second line contains n integers v₁, v₂, ..., v_n representing the value of each node.

Then follow n-1 lines each containing three integers u v w, indicating that there is an undirected edge between node u and node v with weight w.

Each of the next T lines contains four positive integers l₁ r₁ l₂ r₂ representing one query.

outputFormat

For each query, output a single integer representing the maximum value of
\(\left|f(d_{p}-d_{r}, d_{q}-d_{r}, d_{r})\right| + \left|v_{p}-v_{q}\right|\) achievable by choosing two distinct nodes p and q from the given intervals.

sample

3 3
1 3 2
1 2 2
1 3 1
1 2 2 3
1 1 2 3
2 3 2 3

10
10
8