#include <bits/stdc++.h>
using namespace std;
struct Edge {
  long long to, nxt, weigh;
} edge[800100];
struct Point {
  long long f[30], dp1, dp2, dp3, val, dp2sum, dis, sum, depth, pre;
} point[300100];
long long cnt, head[300100], x, y, n, Q, ans;
void addedge(long long x, long long y, long long z) {
  edge[++cnt].to = y;
  edge[cnt].weigh = z;
  edge[cnt].nxt = head[x];
  head[x] = cnt;
}
void dfs1(long long x, long long fa) {
  point[x].f[0] = fa;
  for (long long i = 1; i <= 20; i++)
    point[x].f[i] = point[point[x].f[i - 1]].f[i - 1];
  point[x].sum = point[fa].sum + point[x].val;
  point[x].depth = point[fa].depth + 1;
  for (long long i = head[x]; i; i = edge[i].nxt) {
    long long upup = edge[i].to;
    if (upup == fa) continue;
    point[upup].dis = point[x].dis + edge[i].weigh;
    dfs1(upup, x);
    point[upup].pre = i;
    point[x].dp1 +=
        max(0ll, point[upup].val + point[upup].dp1 - 2 * edge[i].weigh);
  }
  for (long long i = head[x]; i; i = edge[i].nxt) {
    long long upup = edge[i].to;
    if (upup == fa) continue;
    point[upup].dp2 =
        point[x].dp1 -
        max(0ll, point[upup].dp1 + point[upup].val - edge[i].weigh * 2);
  }
}
void dfs2(long long x) {
  point[x].dp2sum = point[point[x].f[0]].dp2sum + point[x].dp2;
  for (long long i = head[x]; i; i = edge[i].nxt) {
    long long upup = edge[i].to;
    if (upup == point[x].f[0]) continue;
    point[upup].dp3 = max(
        point[x].dp3 + point[x].val - edge[i].weigh * 2 + point[upup].dp2, 0ll);
    dfs2(upup);
  }
}
long long LCA(long long x, long long y) {
  if (point[x].depth > point[y].depth) swap(x, y);
  for (long long i = 20; i >= 0; i--)
    if (point[point[y].f[i]].depth >= point[x].depth) y = point[y].f[i];
  if (x == y) return x;
  for (long long i = 20; i >= 0; i--)
    if (point[x].f[i] != point[y].f[i]) x = point[x].f[i], y = point[y].f[i];
  return point[x].f[0];
}
signed main() {
  scanf("%lld%lld", &n, &Q);
  for (long long i = 1; i <= n; i++) scanf("%lld", &point[i].val);
  for (long long i = 1, x, y, z; i < n; i++) {
    scanf("%lld%lld%lld", &x, &y, &z);
    addedge(x, y, z);
    addedge(y, x, z);
  }
  dfs1(1, 0);
  dfs2(1);
  while (Q--) {
    scanf("%lld%lld", &x, &y);
    long long lca = LCA(x, y);
    ans = -point[x].dis - point[y].dis + point[lca].dis * 2;
    ans += point[x].sum + point[y].sum - point[lca].sum -
           point[point[lca].f[0]].sum;
    if (point[x].depth > point[y].depth) swap(x, y);
    if (x == lca) {
      ans += point[x].dp3 + point[y].dp1;
      ans += point[y].dp2sum - point[x].dp2sum;
    } else {
      ans += point[lca].dp3 + point[x].dp1 + point[y].dp1;
      ans += point[x].dp2sum + point[y].dp2sum;
      for (long long i = 20; i >= 0; i--) {
        if (point[point[x].f[i]].depth > point[lca].depth) x = point[x].f[i];
        if (point[point[y].f[i]].depth > point[lca].depth) y = point[y].f[i];
      }
      ans -= point[x].dp2sum + point[y].dp2sum;
      ans += point[x].dp2;
      ans -=
          max(point[y].dp1 + point[y].val - 2 * edge[point[y].pre].weigh, 0ll);
    }
    printf("%lld\n", ans);
  }
}

### Prompt

Please formulate a Cpp solution to the following problem:

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 Pr(p) = ∑_{v ∈ distinct vertices in  p}{a_v} - ∑_{e ∈ distinct edges in  p}{k_e ⋅ 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 Pr(p).

Input

The first line contains two integers n and q (2 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ q ≤ 4 ⋅ 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, ..., a_n (1 ≤ a_i ≤ 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 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 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 ≤ qu_i, qv_i ≤ n) — endpoints of the 2-path you need to find.

Output

For each query print one integer per line — maximal profit Pr(p) of the some 2-path p with the corresponding endpoints.

Example

Input

7 6
6 5 5 3 2 1 2
1 2 2
2 3 2
2 4 1
4 5 1
6 4 2
7 3 25
1 1
4 4
5 6
6 4
3 4
3 7


Output

9
9
9
8
12
-14

Note

Explanation of queries: 

  1. (1, 1) — one of the optimal 2-paths is the following: 1 → 2 → 4 → 5 → 4 → 2 → 3 → 2 → 1. Pr(p) = (a_1 + a_2 + a_3 + a_4 + a_5) - (2 ⋅ w(1,2) + 2 ⋅ w(2,3) + 2 ⋅ w(2,4) + 2 ⋅ w(4,5)) = 21 - 2 ⋅ 12 = 9. 
  2. (4, 4): 4 → 2 → 1 → 2 → 3 → 2 → 4. Pr(p) = (a_1 + a_2 + a_3 + a_4) - 2 ⋅ (w(1,2) + w(2,3) + w(2,4)) = 19 - 2 ⋅ 10 = 9. 
  3. (5, 6): 5 → 4 → 2 → 3 → 2 → 1 → 2 → 4 → 6. 
  4. (6, 4): 6 → 4 → 2 → 1 → 2 → 3 → 2 → 4. 
  5. (3, 4): 3 → 2 → 1 → 2 → 4. 
  6. (3, 7): 3 → 2 → 1 → 2 → 4 → 5 → 4 → 2 → 3 → 7. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge {
  long long to, nxt, weigh;
} edge[800100];
struct Point {
  long long f[30], dp1, dp2, dp3, val, dp2sum, dis, sum, depth, pre;
} point[300100];
long long cnt, head[300100], x, y, n, Q, ans;
void addedge(long long x, long long y, long long z) {
  edge[++cnt].to = y;
  edge[cnt].weigh = z;
  edge[cnt].nxt = head[x];
  head[x] = cnt;
}
void dfs1(long long x, long long fa) {
  point[x].f[0] = fa;
  for (long long i = 1; i <= 20; i++)
    point[x].f[i] = point[point[x].f[i - 1]].f[i - 1];
  point[x].sum = point[fa].sum + point[x].val;
  point[x].depth = point[fa].depth + 1;
  for (long long i = head[x]; i; i = edge[i].nxt) {
    long long upup = edge[i].to;
    if (upup == fa) continue;
    point[upup].dis = point[x].dis + edge[i].weigh;
    dfs1(upup, x);
    point[upup].pre = i;
    point[x].dp1 +=
        max(0ll, point[upup].val + point[upup].dp1 - 2 * edge[i].weigh);
  }
  for (long long i = head[x]; i; i = edge[i].nxt) {
    long long upup = edge[i].to;
    if (upup == fa) continue;
    point[upup].dp2 =
        point[x].dp1 -
        max(0ll, point[upup].dp1 + point[upup].val - edge[i].weigh * 2);
  }
}
void dfs2(long long x) {
  point[x].dp2sum = point[point[x].f[0]].dp2sum + point[x].dp2;
  for (long long i = head[x]; i; i = edge[i].nxt) {
    long long upup = edge[i].to;
    if (upup == point[x].f[0]) continue;
    point[upup].dp3 = max(
        point[x].dp3 + point[x].val - edge[i].weigh * 2 + point[upup].dp2, 0ll);
    dfs2(upup);
  }
}
long long LCA(long long x, long long y) {
  if (point[x].depth > point[y].depth) swap(x, y);
  for (long long i = 20; i >= 0; i--)
    if (point[point[y].f[i]].depth >= point[x].depth) y = point[y].f[i];
  if (x == y) return x;
  for (long long i = 20; i >= 0; i--)
    if (point[x].f[i] != point[y].f[i]) x = point[x].f[i], y = point[y].f[i];
  return point[x].f[0];
}
signed main() {
  scanf("%lld%lld", &n, &Q);
  for (long long i = 1; i <= n; i++) scanf("%lld", &point[i].val);
  for (long long i = 1, x, y, z; i < n; i++) {
    scanf("%lld%lld%lld", &x, &y, &z);
    addedge(x, y, z);
    addedge(y, x, z);
  }
  dfs1(1, 0);
  dfs2(1);
  while (Q--) {
    scanf("%lld%lld", &x, &y);
    long long lca = LCA(x, y);
    ans = -point[x].dis - point[y].dis + point[lca].dis * 2;
    ans += point[x].sum + point[y].sum - point[lca].sum -
           point[point[lca].f[0]].sum;
    if (point[x].depth > point[y].depth) swap(x, y);
    if (x == lca) {
      ans += point[x].dp3 + point[y].dp1;
      ans += point[y].dp2sum - point[x].dp2sum;
    } else {
      ans += point[lca].dp3 + point[x].dp1 + point[y].dp1;
      ans += point[x].dp2sum + point[y].dp2sum;
      for (long long i = 20; i >= 0; i--) {
        if (point[point[x].f[i]].depth > point[lca].depth) x = point[x].f[i];
        if (point[point[y].f[i]].depth > point[lca].depth) y = point[y].f[i];
      }
      ans -= point[x].dp2sum + point[y].dp2sum;
      ans += point[x].dp2;
      ans -=
          max(point[y].dp1 + point[y].val - 2 * edge[point[y].pre].weigh, 0ll);
    }
    printf("%lld\n", ans);
  }
}

```