#include <bits/stdc++.h>
using namespace std;
int n, las[301000], nxt[301000 * 2ll], to[301000 * 2ll],
    tot = 1, fa[301000], deep[301000], dfn[301000], son[301000], sz[301000],
    top[301000], lc[301000][19];
long long v[301000], t[301000 * 10], dat[301000 * 2ll], w[301000], f[301000],
    g[301000];
long long max(long long a, long long b) { return a > b ? a : b; }
void putin(int x, int y, int z) {
  nxt[++tot] = las[x];
  las[x] = tot;
  to[tot] = y;
  dat[tot] = z;
}
void ins(int v, int i, int j, int x, long long y) {
  if (i == j) {
    t[v] = y;
    return;
  }
  int m = (i + j) / 2;
  if (x <= m)
    ins(v + v, i, m, x, y);
  else
    ins(v + v + 1, m + 1, j, x, y);
  t[v] = t[v + v] + t[v + v + 1];
}
void dfs1(int x) {
  sz[x] = 1;
  f[x] = w[x];
  for (int i = las[x]; i; i = nxt[i]) {
    int y = to[i];
    if (y == fa[x]) continue;
    fa[y] = lc[y][0] = x;
    deep[y] = deep[x] + 1;
    v[y] = dat[i];
    dfs1(y);
    if (sz[y] > sz[son[x]]) son[x] = y;
    sz[x] += sz[y];
    f[x] = f[x] + max(0, f[y] - v[y] * 2ll);
  }
}
void dfs2(int x) {
  dfn[x] = ++tot;
  if (son[x] != 0) {
    top[son[x]] = top[x];
    long long fx = f[x] - max(0, f[son[x]] - v[son[x]] * 2ll);
    ins(1, 1, n, dfn[x], fx - v[son[x]]);
    g[son[x]] = max(0, fx + g[x] - v[son[x]] * 2ll);
    dfs2(son[x]);
  }
  for (int i = las[x]; i; i = nxt[i]) {
    int y = to[i];
    if (y == fa[x] || y == son[x]) continue;
    top[y] = y;
    long long fx = f[x] - max(0, f[y] - v[y] * 2ll);
    g[y] = max(0, fx + g[x] - v[y] * 2ll);
    dfs2(y);
  }
}
int lca(int x, int y) {
  if (deep[y] > deep[x]) swap(x, y);
  for (int i = 18; i >= 0; i--)
    if (deep[lc[x][i]] >= deep[y]) x = lc[x][i];
  for (int i = 18; i >= 0; i--)
    if (lc[x][i] != lc[y][i]) x = lc[x][i], y = lc[y][i];
  if (x != y) x = fa[x];
  return x;
}
int downx(int x, int y) {
  for (int i = 18; i >= 0; i--)
    if (deep[lc[y][i]] > deep[x]) y = lc[y][i];
  return y;
}
long long get(int v, int i, int j, int x, int y) {
  if (i == x && j == y) return t[v];
  int m = (i + j) / 2;
  if (y <= m)
    return get(v + v, i, m, x, y);
  else if (x > m)
    return get(v + v + 1, m + 1, j, x, y);
  else
    return get(v + v, i, m, x, m) + get(v + v + 1, m + 1, j, m + 1, y);
}
long long calc(int x, int z) {
  if (deep[x] < deep[z]) return 0;
  long long ans = f[x];
  for (; deep[x] > deep[z];) {
    int y = top[x];
    if (deep[y] < deep[z]) y = z;
    if (x == y) {
      y = fa[x];
      ans = ans + f[y] - max(0, f[x] - 2 * v[x]) - v[x];
      x = y;
    } else {
      ans = ans + get(1, 1, n, dfn[y], dfn[fa[x]]);
      x = y;
    }
  }
  return ans;
}
int main() {
  int ac;
  scanf("%d%d", &n, &ac);
  for (int i = 1; i <= n; i++) scanf("%I64d", &w[i]);
  for (int i = 1; i <= n - 1; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    putin(x, y, z);
    putin(y, x, z);
  }
  tot = 0;
  deep[1] = 1;
  dfs1(1);
  dfs2(1);
  for (int j = 1; j <= 18; j++) {
    for (int i = 1; i <= n; i++) {
      lc[i][j] = lc[lc[i][j - 1]][j - 1];
    }
  }
  while (ac--) {
    int x, y;
    scanf("%d%d", &x, &y);
    int z = lca(x, y), z2 = downx(z, y);
    long long jy = -max(0, f[z2] - v[z2] * 2ll) - v[z2];
    if (y == z)
      jy = 0;
    else
      jy = jy + calc(y, z2);
    printf("%I64d\n", calc(x, z) + g[z] + jy);
  }
}

### Prompt

Your challenge is to write 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;
int n, las[301000], nxt[301000 * 2ll], to[301000 * 2ll],
    tot = 1, fa[301000], deep[301000], dfn[301000], son[301000], sz[301000],
    top[301000], lc[301000][19];
long long v[301000], t[301000 * 10], dat[301000 * 2ll], w[301000], f[301000],
    g[301000];
long long max(long long a, long long b) { return a > b ? a : b; }
void putin(int x, int y, int z) {
  nxt[++tot] = las[x];
  las[x] = tot;
  to[tot] = y;
  dat[tot] = z;
}
void ins(int v, int i, int j, int x, long long y) {
  if (i == j) {
    t[v] = y;
    return;
  }
  int m = (i + j) / 2;
  if (x <= m)
    ins(v + v, i, m, x, y);
  else
    ins(v + v + 1, m + 1, j, x, y);
  t[v] = t[v + v] + t[v + v + 1];
}
void dfs1(int x) {
  sz[x] = 1;
  f[x] = w[x];
  for (int i = las[x]; i; i = nxt[i]) {
    int y = to[i];
    if (y == fa[x]) continue;
    fa[y] = lc[y][0] = x;
    deep[y] = deep[x] + 1;
    v[y] = dat[i];
    dfs1(y);
    if (sz[y] > sz[son[x]]) son[x] = y;
    sz[x] += sz[y];
    f[x] = f[x] + max(0, f[y] - v[y] * 2ll);
  }
}
void dfs2(int x) {
  dfn[x] = ++tot;
  if (son[x] != 0) {
    top[son[x]] = top[x];
    long long fx = f[x] - max(0, f[son[x]] - v[son[x]] * 2ll);
    ins(1, 1, n, dfn[x], fx - v[son[x]]);
    g[son[x]] = max(0, fx + g[x] - v[son[x]] * 2ll);
    dfs2(son[x]);
  }
  for (int i = las[x]; i; i = nxt[i]) {
    int y = to[i];
    if (y == fa[x] || y == son[x]) continue;
    top[y] = y;
    long long fx = f[x] - max(0, f[y] - v[y] * 2ll);
    g[y] = max(0, fx + g[x] - v[y] * 2ll);
    dfs2(y);
  }
}
int lca(int x, int y) {
  if (deep[y] > deep[x]) swap(x, y);
  for (int i = 18; i >= 0; i--)
    if (deep[lc[x][i]] >= deep[y]) x = lc[x][i];
  for (int i = 18; i >= 0; i--)
    if (lc[x][i] != lc[y][i]) x = lc[x][i], y = lc[y][i];
  if (x != y) x = fa[x];
  return x;
}
int downx(int x, int y) {
  for (int i = 18; i >= 0; i--)
    if (deep[lc[y][i]] > deep[x]) y = lc[y][i];
  return y;
}
long long get(int v, int i, int j, int x, int y) {
  if (i == x && j == y) return t[v];
  int m = (i + j) / 2;
  if (y <= m)
    return get(v + v, i, m, x, y);
  else if (x > m)
    return get(v + v + 1, m + 1, j, x, y);
  else
    return get(v + v, i, m, x, m) + get(v + v + 1, m + 1, j, m + 1, y);
}
long long calc(int x, int z) {
  if (deep[x] < deep[z]) return 0;
  long long ans = f[x];
  for (; deep[x] > deep[z];) {
    int y = top[x];
    if (deep[y] < deep[z]) y = z;
    if (x == y) {
      y = fa[x];
      ans = ans + f[y] - max(0, f[x] - 2 * v[x]) - v[x];
      x = y;
    } else {
      ans = ans + get(1, 1, n, dfn[y], dfn[fa[x]]);
      x = y;
    }
  }
  return ans;
}
int main() {
  int ac;
  scanf("%d%d", &n, &ac);
  for (int i = 1; i <= n; i++) scanf("%I64d", &w[i]);
  for (int i = 1; i <= n - 1; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    putin(x, y, z);
    putin(y, x, z);
  }
  tot = 0;
  deep[1] = 1;
  dfs1(1);
  dfs2(1);
  for (int j = 1; j <= 18; j++) {
    for (int i = 1; i <= n; i++) {
      lc[i][j] = lc[lc[i][j - 1]][j - 1];
    }
  }
  while (ac--) {
    int x, y;
    scanf("%d%d", &x, &y);
    int z = lca(x, y), z2 = downx(z, y);
    long long jy = -max(0, f[z2] - v[z2] * 2ll) - v[z2];
    if (y == z)
      jy = 0;
    else
      jy = jy + calc(y, z2);
    printf("%I64d\n", calc(x, z) + g[z] + jy);
  }
}

```