#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long num = 0, neg = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num * neg;
}
long long f[300010], g[300010], f1[300010], val[300010], a[300010], n, Q;
long long dep[300010], fa[300010], size[300010], son[300010], tot;
long long id[300010], rl[300010], v[300010], v1[300010], top[300010];
long long tree[300010 << 2], sum[300010 << 2];
long long cnt, to[600010], nxt[600010], tmp[600010], head[300010];
inline void insert(long long x, long long y, long long z) {
  to[++cnt] = y, nxt[cnt] = head[x], tmp[cnt] = z, head[x] = cnt;
}
inline void push_up(long long x) {
  tree[x] = tree[x << 1] + tree[x << 1 | 1];
  sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
inline void build(long long l, long long r, long long x) {
  if (l == r) {
    tree[x] = v[l] - v1[l], sum[x] = val[rl[l]];
    return;
  }
  long long mid = l + r >> 1;
  build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
  push_up(x);
  return;
}
inline long long query(long long ql, long long qr, long long l, long long r,
                       long long x) {
  if (ql <= l && qr >= r) return tree[x];
  long long mid = l + r >> 1, res = 0;
  if (ql <= mid) res += query(ql, qr, l, mid, x << 1);
  if (qr > mid) res += query(ql, qr, mid + 1, r, x << 1 | 1);
  return res;
}
inline long long qsum(long long ql, long long qr, long long l, long long r,
                      long long x) {
  if (ql <= l && qr >= r) return sum[x];
  long long mid = l + r >> 1, res = 0;
  if (ql <= mid) res += qsum(ql, qr, l, mid, x << 1);
  if (qr > mid) res += qsum(ql, qr, mid + 1, r, x << 1 | 1);
  return res;
}
inline void dfs1(long long u, long long father, long long deep) {
  dep[u] = deep;
  fa[u] = father;
  size[u] = 1;
  long long maxson = 0;
  for (register long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == father) continue;
    dfs1(v, u, deep + 1);
    size[u] += size[v];
    if (size[maxson] < size[v]) maxson = v;
  }
  son[u] = maxson;
  return;
}
inline void dfs2(long long u, long long topfa) {
  id[u] = ++tot;
  rl[tot] = u;
  v[tot] = f[u];
  v1[tot] = f1[u];
  top[u] = topfa;
  if (!son[u]) return;
  dfs2(son[u], topfa);
  for (register long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa[u] || v == son[u]) continue;
    dfs2(v, v);
  }
  return;
}
inline void dfs3(long long u) {
  f[u] = a[u];
  for (long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa[u]) continue;
    dfs3(v);
    val[v] = tmp[i];
    f[u] += max(0ll, f[v] - 2 * val[v]);
    f1[v] = max(0ll, f[v] - 2 * val[v]);
  }
  return;
}
inline void dfs4(long long u) {
  g[u] = max(0ll, g[fa[u]] + f[fa[u]] - f1[u] - 2 * val[u]);
  for (long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa[u]) continue;
    dfs4(v);
  }
  return;
}
inline long long Q_range(long long x, long long y) {
  long long res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    res += query(id[top[x]], id[x], 1, n, 1);
    x = fa[top[x]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  if (x == y)
    return res + f[x] + g[x];
  else
    return res + query(id[x] + 1, id[y], 1, n, 1) + f[x] + g[x];
}
inline long long LCA(long long x, long long y) {
  long long res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    res += qsum(id[top[x]], id[x], 1, n, 1);
    x = fa[top[x]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  if (x != y) res += qsum(id[x] + 1, id[y], 1, n, 1);
  return res;
}
signed main() {
  n = read(), Q = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  long long x, y, z;
  for (long long i = 1; i < n; i++) {
    x = read(), y = read(), z = read();
    insert(x, y, z), insert(y, x, z);
  }
  dfs1(1, 1, 1), dfs3(1), f1[1] = f[1], dfs4(1), dfs2(1, 1);
  build(1, n, 1);
  while (Q--) {
    x = read(), y = read();
    printf("%lld\n", Q_range(x, y) - LCA(x, y));
  }
  return 0;
}

### 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;
inline long long read() {
  long long num = 0, neg = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num * neg;
}
long long f[300010], g[300010], f1[300010], val[300010], a[300010], n, Q;
long long dep[300010], fa[300010], size[300010], son[300010], tot;
long long id[300010], rl[300010], v[300010], v1[300010], top[300010];
long long tree[300010 << 2], sum[300010 << 2];
long long cnt, to[600010], nxt[600010], tmp[600010], head[300010];
inline void insert(long long x, long long y, long long z) {
  to[++cnt] = y, nxt[cnt] = head[x], tmp[cnt] = z, head[x] = cnt;
}
inline void push_up(long long x) {
  tree[x] = tree[x << 1] + tree[x << 1 | 1];
  sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
inline void build(long long l, long long r, long long x) {
  if (l == r) {
    tree[x] = v[l] - v1[l], sum[x] = val[rl[l]];
    return;
  }
  long long mid = l + r >> 1;
  build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
  push_up(x);
  return;
}
inline long long query(long long ql, long long qr, long long l, long long r,
                       long long x) {
  if (ql <= l && qr >= r) return tree[x];
  long long mid = l + r >> 1, res = 0;
  if (ql <= mid) res += query(ql, qr, l, mid, x << 1);
  if (qr > mid) res += query(ql, qr, mid + 1, r, x << 1 | 1);
  return res;
}
inline long long qsum(long long ql, long long qr, long long l, long long r,
                      long long x) {
  if (ql <= l && qr >= r) return sum[x];
  long long mid = l + r >> 1, res = 0;
  if (ql <= mid) res += qsum(ql, qr, l, mid, x << 1);
  if (qr > mid) res += qsum(ql, qr, mid + 1, r, x << 1 | 1);
  return res;
}
inline void dfs1(long long u, long long father, long long deep) {
  dep[u] = deep;
  fa[u] = father;
  size[u] = 1;
  long long maxson = 0;
  for (register long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == father) continue;
    dfs1(v, u, deep + 1);
    size[u] += size[v];
    if (size[maxson] < size[v]) maxson = v;
  }
  son[u] = maxson;
  return;
}
inline void dfs2(long long u, long long topfa) {
  id[u] = ++tot;
  rl[tot] = u;
  v[tot] = f[u];
  v1[tot] = f1[u];
  top[u] = topfa;
  if (!son[u]) return;
  dfs2(son[u], topfa);
  for (register long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa[u] || v == son[u]) continue;
    dfs2(v, v);
  }
  return;
}
inline void dfs3(long long u) {
  f[u] = a[u];
  for (long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa[u]) continue;
    dfs3(v);
    val[v] = tmp[i];
    f[u] += max(0ll, f[v] - 2 * val[v]);
    f1[v] = max(0ll, f[v] - 2 * val[v]);
  }
  return;
}
inline void dfs4(long long u) {
  g[u] = max(0ll, g[fa[u]] + f[fa[u]] - f1[u] - 2 * val[u]);
  for (long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa[u]) continue;
    dfs4(v);
  }
  return;
}
inline long long Q_range(long long x, long long y) {
  long long res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    res += query(id[top[x]], id[x], 1, n, 1);
    x = fa[top[x]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  if (x == y)
    return res + f[x] + g[x];
  else
    return res + query(id[x] + 1, id[y], 1, n, 1) + f[x] + g[x];
}
inline long long LCA(long long x, long long y) {
  long long res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    res += qsum(id[top[x]], id[x], 1, n, 1);
    x = fa[top[x]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  if (x != y) res += qsum(id[x] + 1, id[y], 1, n, 1);
  return res;
}
signed main() {
  n = read(), Q = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  long long x, y, z;
  for (long long i = 1; i < n; i++) {
    x = read(), y = read(), z = read();
    insert(x, y, z), insert(y, x, z);
  }
  dfs1(1, 1, 1), dfs3(1), f1[1] = f[1], dfs4(1), dfs2(1, 1);
  build(1, n, 1);
  while (Q--) {
    x = read(), y = read();
    printf("%lld\n", Q_range(x, y) - LCA(x, y));
  }
  return 0;
}

```