You are given a weighted tree (undirected connected graph with no cycles, loops or multiple edges) with $n$ vertices. The edge ${u_j, v_j}$ has weight $w_j$. Also each vertex $i$ has its own value $a_i$ assigned to it.
Let's call a path starting in vertex $u$ and ending in vertex $v$, where each edge can appear no more than twice (regardless of direction), a _2-path_. Vertices can appear in the 2-path multiple times (even start and end vertices).
For some 2-path $p$ profit $\text{Pr}(p) = \sum\limits_{v \in \text{distinct vertices in } p}{a_v} - \sum\limits_{e \in \text{distinct edges in } p}{k_e \cdot w_e}$, where $k_e$ is the number of times edge $e$ appears in $p$. That is, vertices are counted once, but edges are counted the number of times they appear in $p$.
You are about to answer $m$ queries. Each query is a pair of vertices $(qu, qv)$. For each query find 2-path $p$ from $qu$ to $qv$ with maximal profit $\text{Pr}(p)$.
## Input
The first line contains two integers $n$ and $q$ ($2 \le n \le 3 \cdot 10^5$, $1 \le q \le 4 \cdot 10^5$) — the number of vertices in the tree and the number of queries.
The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$ — the values of the vertices.
Next $n - 1$ lines contain descriptions of edges: each line contains three space separated integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 10^9$) — there is edge ${u_i, v_i}$ with weight $w_i$ in the tree.
Next $q$ lines contain queries (one per line). Each query contains two integers $qu_i$ and $qv_i$ $(1 \le qu_i, qv_i \le n)$ — endpoints of the 2-path you need to find.
## Output
For each query print one integer per line — maximal profit $\text{Pr}(p)$ of the some 2-path $p$ with the corresponding endpoints.
[samples]
## Note
Explanation of queries:
1. $(1, 1)$ — one of the optimal 2-paths is the following: $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$. $\text{Pr}(p) = (a_1 + a_2 + a_3 + a_4 + a_5) - (2 \cdot w(1,2) + 2 \cdot w(2,3) + 2 \cdot w(2,4) + 2 \cdot w(4,5)) = 21 - 2 \cdot 12 = 9$.
2. $(4, 4)$: $4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$. $\text{Pr}(p) = (a_1 + a_2 + a_3 + a_4) - 2 \cdot (w(1,2) + w(2,3) + w(2,4)) = 19 - 2 \cdot 10 = 9$.
3. $(5, 6)$: $5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 6$.
4. $(6, 4)$: $6 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$.
5. $(3, 4)$: $3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4$.
6. $(3, 7)$: $3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 7$.
[samples]
## Note
查询说明：
$(1, 1)$：其中一个最优 2-path 如下：$1 \to 2 \to 4 \to 5 \to 4 \to 2 \to 3 \to 2 \to 1$。$"Pr"(p) = (a_1 + a_2 + a_3 + a_4 + a_5) - (2 \cdot w(1, 2) + 2 \cdot w(2, 3) + 2 \cdot w(2, 4) + 2 \cdot w(4, 5)) = 21 - 2 \cdot 12 = 9$。
$(4, 4)$：$4 \to 2 \to 1 \to 2 \to 3 \to 2 \to 4$。$"Pr"(p) = (a_1 + a_2 + a_3 + a_4) - 2 \cdot (w(1, 2) + w(2, 3) + w(2, 4)) = 19 - 2 \cdot 10 = 9$。
$(5, 6)$：$5 \to 4 \to 2 \to 3 \to 2 \to 1 \to 2 \to 4 \to 6$。
$(6, 4)$：$6 \to 4 \to 2 \to 1 \to 2 \to 3 \to 2 \to 4$。
$(3, 4)$：$3 \to 2 \to 1 \to 2 \to 4$。
$(3, 7)$：$3 \to 2 \to 1 \to 2 \to 4 \to 5 \to 4 \to 2 \to 3 \to 7$。
**Definitions**
Let $ T = (V, E) $ be a tree with $ n = |V| $ vertices and $ n-1 $ edges.
Let $ a_i \in \mathbb{R}^+ $ be the value assigned to vertex $ i \in V $.
Let $ w_e \in \mathbb{R}^+ $ be the weight of edge $ e \in E $.
A **2-path** $ p $ between vertices $ u $ and $ v $ is a walk (sequence of vertices and edges) from $ u $ to $ v $ such that each edge is traversed at most twice (in either direction).
Define the **profit** of a 2-path $ p $ as:
$$
\text{Pr}(p) = \sum_{v \in \text{distinct vertices in } p} a_v - \sum_{e \in E} k_e \cdot w_e
$$
where $ k_e \in \{0,1,2\} $ is the number of times edge $ e $ is traversed in $ p $.
**Constraints**
1. $ 2 \le n \le 3 \cdot 10^5 $
2. $ 1 \le q \le 4 \cdot 10^5 $
3. $ 1 \le a_i \le 10^9 $ for all $ i \in V $
4. $ 1 \le w_e \le 10^9 $ for all $ e \in E $
5. For each query $ (q_u, q_v) $, $ q_u, q_v \in V $
**Objective**
For each query $ (u, v) $, compute:
$$
\max_{p: u \leadsto v} \left( \sum_{x \in \text{vertices}(p)} a_x - \sum_{e \in E} k_e \cdot w_e \right)
$$
where the maximum is taken over all 2-paths $ p $ from $ u $ to $ v $.