#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast", "-funroll-loops", "-fdelete-null-pointer-checks")
#pragma GCC target("ssse3", "sse3", "sse2", "sse", "avx2", "avx")
using std::max;
using std::sort;
const int MAXN = 3e5 + 50, MAXQ = 4e5 + 50;
int Lct_c[2][MAXN], Lct_fa[MAXN];
long long Lct_sum1[MAXN], Lct_val1[MAXN], Lct_sum2[MAXN], Lct_val2[MAXN];
bool rev[MAXN];
inline void pushdown(const int &x) {
  if (rev[x]) {
    rev[Lct_c[0][x]] ^= 1, rev[Lct_c[1][x]] ^= 1;
    Lct_c[0][x] ^= Lct_c[1][x] ^= Lct_c[0][x] ^= Lct_c[1][x];
    rev[x] = 0;
  }
}
inline void pushup(const int &x) {
  Lct_sum1[x] = Lct_sum1[Lct_c[0][x]] + Lct_sum1[Lct_c[1][x]] + Lct_val1[x];
  Lct_sum2[x] = Lct_sum2[Lct_c[0][x]] + Lct_sum2[Lct_c[1][x]] + Lct_val2[x];
}
inline bool isroot(const int &x) {
  return ((Lct_c[0][Lct_fa[x]] != x && Lct_c[1][Lct_fa[x]] != x) ||
          Lct_fa[x] == 0);
}
inline bool rotate_get(const int &x) { return (Lct_c[1][Lct_fa[x]] == x); }
inline void rotate(int x) {
  bool r = rotate_get(x), rf = rotate_get(Lct_fa[x]);
  int y = Lct_fa[x], z = Lct_fa[y], a = Lct_c[!r][x];
  Lct_fa[x] = z;
  if (!isroot(y)) Lct_c[rf][z] = x;
  Lct_fa[y] = x, Lct_c[!r][x] = y;
  Lct_fa[a] = y, Lct_c[r][y] = a;
  pushup(y);
}
void pushall(int x) {
  if (!isroot(x)) pushall(Lct_fa[x]);
  pushdown(x);
}
void splay(int x) {
  pushall(x);
  for (; !isroot(x); rotate(x))
    if (!isroot(Lct_fa[x]))
      rotate((rotate_get(Lct_fa[x]) == rotate_get(x)) ? Lct_fa[x] : x);
  pushup(x);
}
void access(int x) {
  for (int pre = 0; x; pre = x, x = Lct_fa[x]) {
    splay(x);
    Lct_c[1][x] = pre;
    pushup(x);
  }
}
inline void setroot(int x) {
  access(x), splay(x);
  rev[x] = 1;
}
inline void link(int x, int y) {
  setroot(x);
  Lct_fa[x] = y;
}
inline long long Lct_query1(int x, int y) {
  setroot(x), access(y), splay(y);
  return Lct_sum1[y];
}
inline long long Lct_query2(int x, int y) {
  setroot(x), access(y), splay(y);
  return Lct_sum2[y];
}
inline void updata(int x, const long long &val1, const long long &val2) {
  splay(x);
  Lct_val1[x] = val1, Lct_val2[x] = val2;
  pushup(x);
}
int first[MAXN], tote;
struct edge {
  int to, net, w;
} e[MAXN << 1];
inline void addedge(const int &u, const int &v, const int &w) {
  ++tote;
  e[tote].to = v, e[tote].net = first[u], e[tote].w = w;
  first[u] = tote;
  ++tote;
  e[tote].to = u, e[tote].net = first[v], e[tote].w = w;
  first[v] = tote;
}
int dfn[MAXN], tot;
struct Query {
  int x, y, qid;
} query[MAXQ];
long long Ans[MAXQ];
int cur_q;
bool cmp(const Query &A, const Query &B) { return dfn[A.x] < dfn[B.x]; }
int a[MAXN], w_fa[MAXN];
long long dp[MAXN];
void dfs1(int u, int fa) {
  dfn[u] = tot++;
  dp[u] = a[u];
  for (int l = first[u]; l; l = e[l].net)
    if (e[l].to != fa) {
      w_fa[e[l].to] = e[l].w;
      dfs1(e[l].to, u);
      if (dp[e[l].to] - 2 * e[l].w > 0) dp[u] += dp[e[l].to] - 2 * e[l].w;
    }
}
void dfs2(int u, int fa) {
  while (query[cur_q].x == u) {
    int y = query[cur_q].y;
    Ans[query[cur_q].qid] = Lct_query1(u, y) - (Lct_query2(u, y));
    ++cur_q;
  }
  for (int l = first[u]; l; l = e[l].net)
    if (e[l].to != fa) {
      long long delta1 = max(0ll, dp[e[l].to] - 2 * w_fa[e[l].to]);
      dp[u] -= delta1;
      w_fa[u] ^= w_fa[e[l].to] ^= w_fa[u] ^= w_fa[e[l].to];
      long long delta2 = max(0ll, dp[u] - 2 * w_fa[u]);
      dp[e[l].to] += delta2;
      updata(u, dp[u], w_fa[u] + delta2);
      updata(e[l].to, dp[e[l].to], 0);
      dfs2(e[l].to, u);
      dp[u] += delta1;
      w_fa[u] ^= w_fa[e[l].to] ^= w_fa[u] ^= w_fa[e[l].to];
      dp[e[l].to] -= delta2;
      updata(u, dp[u], 0);
      updata(e[l].to, dp[e[l].to], w_fa[e[l].to] + delta1);
    }
}
inline int read() {
  int x = 0;
  char c = getchar();
  bool f = 0;
  while (c < '0' || c > '9') (c == '-') ? f = 1, c = getchar() : c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (48 ^ c), c = getchar();
  return (f) ? -x : x;
}
int main() {
  int n = read(), q = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 0; i < n - 1; ++i) {
    int u = read(), v = read(), w = read();
    addedge(u, v, w);
  }
  for (int i = 0; i < q; ++i) {
    query[i].x = read(), query[i].y = read();
    if (dfn[query[i].x] > dfn[query[i].y])
      query[i].x ^= query[i].y ^= query[i].x ^= query[i].y;
    query[i].qid = i;
  }
  dfs1(1, 0);
  for (int x = 1; x <= n; ++x) {
    Lct_val1[x] = Lct_sum1[x] = dp[x];
    Lct_val2[x] = w_fa[x];
    if (x != 1 && dp[x] - 2 * w_fa[x] > 0) {
      Lct_val2[x] += dp[x] - 2 * w_fa[x];
      Lct_sum2[x] += dp[x] - 2 * w_fa[x];
    }
  }
  for (int i = 1; i <= tote; i += 2) link(e[i].to, e[i + 1].to);
  sort(query, query + q, cmp);
  dfs2(1, 0);
  for (int i = 0; i < q; ++i) printf("%lld\n", Ans[i]);
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast", "-funroll-loops", "-fdelete-null-pointer-checks")
#pragma GCC target("ssse3", "sse3", "sse2", "sse", "avx2", "avx")
using std::max;
using std::sort;
const int MAXN = 3e5 + 50, MAXQ = 4e5 + 50;
int Lct_c[2][MAXN], Lct_fa[MAXN];
long long Lct_sum1[MAXN], Lct_val1[MAXN], Lct_sum2[MAXN], Lct_val2[MAXN];
bool rev[MAXN];
inline void pushdown(const int &x) {
  if (rev[x]) {
    rev[Lct_c[0][x]] ^= 1, rev[Lct_c[1][x]] ^= 1;
    Lct_c[0][x] ^= Lct_c[1][x] ^= Lct_c[0][x] ^= Lct_c[1][x];
    rev[x] = 0;
  }
}
inline void pushup(const int &x) {
  Lct_sum1[x] = Lct_sum1[Lct_c[0][x]] + Lct_sum1[Lct_c[1][x]] + Lct_val1[x];
  Lct_sum2[x] = Lct_sum2[Lct_c[0][x]] + Lct_sum2[Lct_c[1][x]] + Lct_val2[x];
}
inline bool isroot(const int &x) {
  return ((Lct_c[0][Lct_fa[x]] != x && Lct_c[1][Lct_fa[x]] != x) ||
          Lct_fa[x] == 0);
}
inline bool rotate_get(const int &x) { return (Lct_c[1][Lct_fa[x]] == x); }
inline void rotate(int x) {
  bool r = rotate_get(x), rf = rotate_get(Lct_fa[x]);
  int y = Lct_fa[x], z = Lct_fa[y], a = Lct_c[!r][x];
  Lct_fa[x] = z;
  if (!isroot(y)) Lct_c[rf][z] = x;
  Lct_fa[y] = x, Lct_c[!r][x] = y;
  Lct_fa[a] = y, Lct_c[r][y] = a;
  pushup(y);
}
void pushall(int x) {
  if (!isroot(x)) pushall(Lct_fa[x]);
  pushdown(x);
}
void splay(int x) {
  pushall(x);
  for (; !isroot(x); rotate(x))
    if (!isroot(Lct_fa[x]))
      rotate((rotate_get(Lct_fa[x]) == rotate_get(x)) ? Lct_fa[x] : x);
  pushup(x);
}
void access(int x) {
  for (int pre = 0; x; pre = x, x = Lct_fa[x]) {
    splay(x);
    Lct_c[1][x] = pre;
    pushup(x);
  }
}
inline void setroot(int x) {
  access(x), splay(x);
  rev[x] = 1;
}
inline void link(int x, int y) {
  setroot(x);
  Lct_fa[x] = y;
}
inline long long Lct_query1(int x, int y) {
  setroot(x), access(y), splay(y);
  return Lct_sum1[y];
}
inline long long Lct_query2(int x, int y) {
  setroot(x), access(y), splay(y);
  return Lct_sum2[y];
}
inline void updata(int x, const long long &val1, const long long &val2) {
  splay(x);
  Lct_val1[x] = val1, Lct_val2[x] = val2;
  pushup(x);
}
int first[MAXN], tote;
struct edge {
  int to, net, w;
} e[MAXN << 1];
inline void addedge(const int &u, const int &v, const int &w) {
  ++tote;
  e[tote].to = v, e[tote].net = first[u], e[tote].w = w;
  first[u] = tote;
  ++tote;
  e[tote].to = u, e[tote].net = first[v], e[tote].w = w;
  first[v] = tote;
}
int dfn[MAXN], tot;
struct Query {
  int x, y, qid;
} query[MAXQ];
long long Ans[MAXQ];
int cur_q;
bool cmp(const Query &A, const Query &B) { return dfn[A.x] < dfn[B.x]; }
int a[MAXN], w_fa[MAXN];
long long dp[MAXN];
void dfs1(int u, int fa) {
  dfn[u] = tot++;
  dp[u] = a[u];
  for (int l = first[u]; l; l = e[l].net)
    if (e[l].to != fa) {
      w_fa[e[l].to] = e[l].w;
      dfs1(e[l].to, u);
      if (dp[e[l].to] - 2 * e[l].w > 0) dp[u] += dp[e[l].to] - 2 * e[l].w;
    }
}
void dfs2(int u, int fa) {
  while (query[cur_q].x == u) {
    int y = query[cur_q].y;
    Ans[query[cur_q].qid] = Lct_query1(u, y) - (Lct_query2(u, y));
    ++cur_q;
  }
  for (int l = first[u]; l; l = e[l].net)
    if (e[l].to != fa) {
      long long delta1 = max(0ll, dp[e[l].to] - 2 * w_fa[e[l].to]);
      dp[u] -= delta1;
      w_fa[u] ^= w_fa[e[l].to] ^= w_fa[u] ^= w_fa[e[l].to];
      long long delta2 = max(0ll, dp[u] - 2 * w_fa[u]);
      dp[e[l].to] += delta2;
      updata(u, dp[u], w_fa[u] + delta2);
      updata(e[l].to, dp[e[l].to], 0);
      dfs2(e[l].to, u);
      dp[u] += delta1;
      w_fa[u] ^= w_fa[e[l].to] ^= w_fa[u] ^= w_fa[e[l].to];
      dp[e[l].to] -= delta2;
      updata(u, dp[u], 0);
      updata(e[l].to, dp[e[l].to], w_fa[e[l].to] + delta1);
    }
}
inline int read() {
  int x = 0;
  char c = getchar();
  bool f = 0;
  while (c < '0' || c > '9') (c == '-') ? f = 1, c = getchar() : c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (48 ^ c), c = getchar();
  return (f) ? -x : x;
}
int main() {
  int n = read(), q = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 0; i < n - 1; ++i) {
    int u = read(), v = read(), w = read();
    addedge(u, v, w);
  }
  for (int i = 0; i < q; ++i) {
    query[i].x = read(), query[i].y = read();
    if (dfn[query[i].x] > dfn[query[i].y])
      query[i].x ^= query[i].y ^= query[i].x ^= query[i].y;
    query[i].qid = i;
  }
  dfs1(1, 0);
  for (int x = 1; x <= n; ++x) {
    Lct_val1[x] = Lct_sum1[x] = dp[x];
    Lct_val2[x] = w_fa[x];
    if (x != 1 && dp[x] - 2 * w_fa[x] > 0) {
      Lct_val2[x] += dp[x] - 2 * w_fa[x];
      Lct_sum2[x] += dp[x] - 2 * w_fa[x];
    }
  }
  for (int i = 1; i <= tote; i += 2) link(e[i].to, e[i + 1].to);
  sort(query, query + q, cmp);
  dfs2(1, 0);
  for (int i = 0; i < q; ++i) printf("%lld\n", Ans[i]);
}

```