#include <bits/stdc++.h>
using namespace std;
const long long maxn = 3e5 + 20;
long long f[maxn], h[maxn], g[maxn], gsum[maxn];
long long n, m, head[maxn];
long long val[maxn], contribution[maxn];
long long gmmx[maxn], gmx[maxn];
long long valsum[maxn];
long long dis[maxn];
long long dep[maxn];
long long fat[25][maxn], size;
struct edge {
  long long next, to, dis;
} e[maxn << 1];
inline void addedge(long long next, long long to, long long dis) {
  e[++size].to = to;
  e[size].dis = dis;
  e[size].next = head[next];
  head[next] = size;
}
void dfs1(long long t, long long ffat) {
  long long profit = 0;
  long long i, j, k;
  fat[0][t] = ffat;
  dep[t] = dep[ffat] + 1;
  valsum[t] += val[t];
  for (i = head[t]; i; i = e[i].next) {
    j = e[i].to;
    k = e[i].dis;
    if (j == ffat) continue;
    dis[j] = dis[t] + k;
    valsum[j] = valsum[t];
    dfs1(j, t);
    if (f[j] - 2 * k + val[j] > 0) {
      contribution[j] = 1;
      profit = f[j] - 2 * k + val[j];
      f[t] += profit;
    }
  }
  for (i = head[t]; i; i = e[i].next) {
    j = e[i].to;
    k = e[i].dis;
    if (j == ffat) continue;
    if (contribution[j]) {
      profit = f[j] + val[j] - 2 * k;
      g[j] = f[t] - profit;
    } else
      g[j] = f[t];
    if (g[j] >= g[gmmx[t]])
      gmx[t] = gmmx[t], gmmx[t] = j;
    else if (g[j] >= g[gmx[t]])
      gmx[t] = j;
  }
}
void dfs2(long long t, long long ffat) {
  long long i, j, k;
  gsum[t] += g[t];
  for (long long i = 1; i <= 20; i++) {
    fat[i][t] = fat[i - 1][fat[i - 1][t]];
  }
  for (i = head[t]; i; i = e[i].next) {
    j = e[i].to;
    k = e[i].dis;
    if (j == ffat) continue;
    gsum[j] += gsum[t];
    if (j == gmmx[t])
      h[j] = max(-k * 2 + val[t] + h[t] + g[j], h[j]);
    else
      h[j] = max(-k * 2 + val[t] + h[t] + g[j], h[j]);
    dfs2(j, t);
  }
}
long long getlca(long long x, long long y) {
  if (x == y) return x;
  if (dep[x] < dep[y]) swap(x, y);
  long long delta = dep[x] - dep[y];
  if (dep[x] > dep[y])
    for (long long i = 20; i >= 0; i--)
      if (delta >= (1 << i)) delta -= (1 << i), x = fat[i][x];
  for (long long i = 20; i >= 0; i--) {
    if (fat[i][x] != fat[i][y]) {
      x = fat[i][x];
      y = fat[i][y];
    }
  }
  if (x == y) return x;
  return fat[0][x];
}
long long fakelca(long long x, long long y) {
  if (x == y) return 0;
  if (dep[x] < dep[y]) swap(x, y);
  for (long long i = 20; i >= 0; i--) {
    if (dep[fat[i][x]] > dep[y]) {
      x = fat[i][x];
    }
  }
  return x;
}
long long getans(long long x, long long y) {
  long long mustans = 0;
  if (dep[x] > dep[y]) swap(x, y);
  long long lca = getlca(x, y);
  if (lca == 1)
    mustans -= dis[x] + dis[y] - dis[lca],
        mustans += valsum[y] + valsum[x] - valsum[lca];
  else
    mustans -= dis[x] + dis[y] - 2 * dis[lca],
        mustans += valsum[y] + valsum[x] - valsum[lca] - valsum[fat[0][lca]];
  if (x == lca) {
    return gsum[y] - gsum[x] + h[x] + f[y] + mustans;
  }
  long long l1, l2;
  l1 = fakelca(x, lca);
  l2 = fakelca(y, lca);
  mustans += f[x] + f[y] + h[lca];
  mustans += gsum[x] - gsum[l1] + gsum[y] - gsum[l2];
  mustans += g[l1];
  if (contribution[l2]) {
    mustans -= f[l2] + val[l2] - 2 * (dis[l2] - dis[lca]);
  }
  return mustans;
}
inline void qread(long long &ans) {
  ans = 0;
  long long f = 1;
  static char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) ans = ans * 10 + c - '0', c = getchar();
  ans = ans * f;
}
signed main() {
  register long long i, j;
  qread(n);
  qread(m);
  long long t1, t2, t3;
  for (i = 1; i <= n; i++) qread(val[i]);
  for (i = 1; i < n; i++) {
    qread(t1);
    qread(t2);
    qread(t3);
    addedge(t1, t2, t3);
    addedge(t2, t1, t3);
  }
  dfs1(1, 0);
  dfs2(1, 0);
  for (i = 1; i <= m; i++) {
    qread(t1);
    qread(t2);
    printf("%lld\n", getans(t1, t2));
  }
  return 0;
}

### Prompt

Your task is to create 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;
const long long maxn = 3e5 + 20;
long long f[maxn], h[maxn], g[maxn], gsum[maxn];
long long n, m, head[maxn];
long long val[maxn], contribution[maxn];
long long gmmx[maxn], gmx[maxn];
long long valsum[maxn];
long long dis[maxn];
long long dep[maxn];
long long fat[25][maxn], size;
struct edge {
  long long next, to, dis;
} e[maxn << 1];
inline void addedge(long long next, long long to, long long dis) {
  e[++size].to = to;
  e[size].dis = dis;
  e[size].next = head[next];
  head[next] = size;
}
void dfs1(long long t, long long ffat) {
  long long profit = 0;
  long long i, j, k;
  fat[0][t] = ffat;
  dep[t] = dep[ffat] + 1;
  valsum[t] += val[t];
  for (i = head[t]; i; i = e[i].next) {
    j = e[i].to;
    k = e[i].dis;
    if (j == ffat) continue;
    dis[j] = dis[t] + k;
    valsum[j] = valsum[t];
    dfs1(j, t);
    if (f[j] - 2 * k + val[j] > 0) {
      contribution[j] = 1;
      profit = f[j] - 2 * k + val[j];
      f[t] += profit;
    }
  }
  for (i = head[t]; i; i = e[i].next) {
    j = e[i].to;
    k = e[i].dis;
    if (j == ffat) continue;
    if (contribution[j]) {
      profit = f[j] + val[j] - 2 * k;
      g[j] = f[t] - profit;
    } else
      g[j] = f[t];
    if (g[j] >= g[gmmx[t]])
      gmx[t] = gmmx[t], gmmx[t] = j;
    else if (g[j] >= g[gmx[t]])
      gmx[t] = j;
  }
}
void dfs2(long long t, long long ffat) {
  long long i, j, k;
  gsum[t] += g[t];
  for (long long i = 1; i <= 20; i++) {
    fat[i][t] = fat[i - 1][fat[i - 1][t]];
  }
  for (i = head[t]; i; i = e[i].next) {
    j = e[i].to;
    k = e[i].dis;
    if (j == ffat) continue;
    gsum[j] += gsum[t];
    if (j == gmmx[t])
      h[j] = max(-k * 2 + val[t] + h[t] + g[j], h[j]);
    else
      h[j] = max(-k * 2 + val[t] + h[t] + g[j], h[j]);
    dfs2(j, t);
  }
}
long long getlca(long long x, long long y) {
  if (x == y) return x;
  if (dep[x] < dep[y]) swap(x, y);
  long long delta = dep[x] - dep[y];
  if (dep[x] > dep[y])
    for (long long i = 20; i >= 0; i--)
      if (delta >= (1 << i)) delta -= (1 << i), x = fat[i][x];
  for (long long i = 20; i >= 0; i--) {
    if (fat[i][x] != fat[i][y]) {
      x = fat[i][x];
      y = fat[i][y];
    }
  }
  if (x == y) return x;
  return fat[0][x];
}
long long fakelca(long long x, long long y) {
  if (x == y) return 0;
  if (dep[x] < dep[y]) swap(x, y);
  for (long long i = 20; i >= 0; i--) {
    if (dep[fat[i][x]] > dep[y]) {
      x = fat[i][x];
    }
  }
  return x;
}
long long getans(long long x, long long y) {
  long long mustans = 0;
  if (dep[x] > dep[y]) swap(x, y);
  long long lca = getlca(x, y);
  if (lca == 1)
    mustans -= dis[x] + dis[y] - dis[lca],
        mustans += valsum[y] + valsum[x] - valsum[lca];
  else
    mustans -= dis[x] + dis[y] - 2 * dis[lca],
        mustans += valsum[y] + valsum[x] - valsum[lca] - valsum[fat[0][lca]];
  if (x == lca) {
    return gsum[y] - gsum[x] + h[x] + f[y] + mustans;
  }
  long long l1, l2;
  l1 = fakelca(x, lca);
  l2 = fakelca(y, lca);
  mustans += f[x] + f[y] + h[lca];
  mustans += gsum[x] - gsum[l1] + gsum[y] - gsum[l2];
  mustans += g[l1];
  if (contribution[l2]) {
    mustans -= f[l2] + val[l2] - 2 * (dis[l2] - dis[lca]);
  }
  return mustans;
}
inline void qread(long long &ans) {
  ans = 0;
  long long f = 1;
  static char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) ans = ans * 10 + c - '0', c = getchar();
  ans = ans * f;
}
signed main() {
  register long long i, j;
  qread(n);
  qread(m);
  long long t1, t2, t3;
  for (i = 1; i <= n; i++) qread(val[i]);
  for (i = 1; i < n; i++) {
    qread(t1);
    qread(t2);
    qread(t3);
    addedge(t1, t2, t3);
    addedge(t2, t1, t3);
  }
  dfs1(1, 0);
  dfs2(1, 0);
  for (i = 1; i <= m; i++) {
    qread(t1);
    qread(t2);
    printf("%lld\n", getans(t1, t2));
  }
  return 0;
}

```