#include <bits/stdc++.h>
using namespace std;
template <class T>
void read(T& x) {
  T f = 1;
  x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
template <class T>
void print(T x, char c) {
  if (x < 0) putchar('-'), x = -x;
  int s[20], top = 0;
  while (s[++top] = x % 10, x /= 10)
    ;
  while (top) putchar(s[top--] + '0');
  putchar(c);
}
int n, m, cnt = 1, h[300005], val[300005];
long long sum[300005], disup[300005], disdown[300005], len[300005], w[300005],
    g[300005], con[300005], ssh[300005];
struct Edge {
  int to, next, w;
} a[300005 << 1];
void Add(int x, int y, int z) {
  cnt++;
  a[cnt].to = y;
  a[cnt].next = h[x];
  a[cnt].w = z;
  h[x] = cnt;
}
int dep[300005], Log[300005], p[300005][19];
void dfs1(int x, int f) {
  p[x][0] = f;
  dep[x] = dep[f] + 1;
  sum[x] = sum[f] + val[x];
  for (int i = 1; i <= Log[dep[x]]; ++i) p[x][i] = p[p[x][i - 1]][i - 1];
  for (int i = h[x], y; i; i = a[i].next)
    if ((y = a[i].to) != f) {
      disdown[y] = disdown[x] + a[i].w;
      disup[y] = disup[x] + a[i ^ 1].w;
      len[y] = a[i].w + a[i ^ 1].w;
      dfs1(y, x);
    }
}
void DP(int x) {
  for (int i = h[x], y; i; i = a[i].next)
    if ((y = a[i].to) != p[x][0])
      DP(y), con[y] = max(0ll, g[y] + val[y] - len[y]), g[x] += con[y];
  for (int i = h[x], y; i; i = a[i].next)
    if ((y = a[i].to) != p[x][0]) w[y] = g[x] - con[y];
}
void presum(int x) {
  w[x] += w[p[x][0]];
  for (int i = h[x], y; i; i = a[i].next)
    if ((y = a[i].to) != p[x][0]) {
      ssh[y] = g[y] + max(0ll, ssh[x] - con[y] + val[x] - len[y]);
      presum(y);
    }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int k = Log[dep[x] - dep[y]]; ~k; --k)
    if (dep[p[x][k]] >= dep[y]) x = p[x][k];
  if (x == y) return x;
  for (int k = Log[dep[x]]; ~k; --k)
    if (p[x][k] != p[y][k]) x = p[x][k], y = p[y][k];
  return p[x][0];
}
int getson(int x, int tp) {
  for (int k = Log[dep[x] - dep[tp] - 1]; ~k; --k)
    if (dep[p[x][k]] > dep[tp]) x = p[x][k];
  return x;
}
int main() {
  read(n);
  read(m);
  for (int i = 1; i <= n; ++i) read(val[i]);
  for (int i = 2; i <= n; ++i) Log[i] = Log[i / 2] + 1;
  for (int i = 1, x, y, a, b; i < n; ++i)
    read(x), read(y), read(b), Add(x, y, b), Add(y, x, b);
  dep[0] = -1;
  dfs1(1, 0);
  DP(1);
  ssh[1] = g[1];
  presum(1);
  while (m--) {
    int u, v, z, A, B;
    read(u), read(v);
    z = lca(u, v);
    long long ans = sum[u] + sum[v] - sum[z] - sum[p[z][0]];
    ans -= disup[u] - disup[z];
    ans -= disdown[v] - disdown[z];
    ans += ssh[z] - g[z];
    if (u != z && v != z) {
      A = getson(u, z), B = getson(v, z);
      ans += g[u] + g[v];
      ans += w[u] - w[A] + w[v] - w[B];
      ans += g[z] - con[A] - con[B];
    } else if (u != z) {
      ans += g[u];
      ans += w[u] - w[z];
    } else if (v != z) {
      ans += g[v];
      ans += w[v] - w[z];
    } else
      ans += g[z];
    print(ans, '\n');
  }
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
template <class T>
void read(T& x) {
  T f = 1;
  x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
template <class T>
void print(T x, char c) {
  if (x < 0) putchar('-'), x = -x;
  int s[20], top = 0;
  while (s[++top] = x % 10, x /= 10)
    ;
  while (top) putchar(s[top--] + '0');
  putchar(c);
}
int n, m, cnt = 1, h[300005], val[300005];
long long sum[300005], disup[300005], disdown[300005], len[300005], w[300005],
    g[300005], con[300005], ssh[300005];
struct Edge {
  int to, next, w;
} a[300005 << 1];
void Add(int x, int y, int z) {
  cnt++;
  a[cnt].to = y;
  a[cnt].next = h[x];
  a[cnt].w = z;
  h[x] = cnt;
}
int dep[300005], Log[300005], p[300005][19];
void dfs1(int x, int f) {
  p[x][0] = f;
  dep[x] = dep[f] + 1;
  sum[x] = sum[f] + val[x];
  for (int i = 1; i <= Log[dep[x]]; ++i) p[x][i] = p[p[x][i - 1]][i - 1];
  for (int i = h[x], y; i; i = a[i].next)
    if ((y = a[i].to) != f) {
      disdown[y] = disdown[x] + a[i].w;
      disup[y] = disup[x] + a[i ^ 1].w;
      len[y] = a[i].w + a[i ^ 1].w;
      dfs1(y, x);
    }
}
void DP(int x) {
  for (int i = h[x], y; i; i = a[i].next)
    if ((y = a[i].to) != p[x][0])
      DP(y), con[y] = max(0ll, g[y] + val[y] - len[y]), g[x] += con[y];
  for (int i = h[x], y; i; i = a[i].next)
    if ((y = a[i].to) != p[x][0]) w[y] = g[x] - con[y];
}
void presum(int x) {
  w[x] += w[p[x][0]];
  for (int i = h[x], y; i; i = a[i].next)
    if ((y = a[i].to) != p[x][0]) {
      ssh[y] = g[y] + max(0ll, ssh[x] - con[y] + val[x] - len[y]);
      presum(y);
    }
}
int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int k = Log[dep[x] - dep[y]]; ~k; --k)
    if (dep[p[x][k]] >= dep[y]) x = p[x][k];
  if (x == y) return x;
  for (int k = Log[dep[x]]; ~k; --k)
    if (p[x][k] != p[y][k]) x = p[x][k], y = p[y][k];
  return p[x][0];
}
int getson(int x, int tp) {
  for (int k = Log[dep[x] - dep[tp] - 1]; ~k; --k)
    if (dep[p[x][k]] > dep[tp]) x = p[x][k];
  return x;
}
int main() {
  read(n);
  read(m);
  for (int i = 1; i <= n; ++i) read(val[i]);
  for (int i = 2; i <= n; ++i) Log[i] = Log[i / 2] + 1;
  for (int i = 1, x, y, a, b; i < n; ++i)
    read(x), read(y), read(b), Add(x, y, b), Add(y, x, b);
  dep[0] = -1;
  dfs1(1, 0);
  DP(1);
  ssh[1] = g[1];
  presum(1);
  while (m--) {
    int u, v, z, A, B;
    read(u), read(v);
    z = lca(u, v);
    long long ans = sum[u] + sum[v] - sum[z] - sum[p[z][0]];
    ans -= disup[u] - disup[z];
    ans -= disdown[v] - disdown[z];
    ans += ssh[z] - g[z];
    if (u != z && v != z) {
      A = getson(u, z), B = getson(v, z);
      ans += g[u] + g[v];
      ans += w[u] - w[A] + w[v] - w[B];
      ans += g[z] - con[A] - con[B];
    } else if (u != z) {
      ans += g[u];
      ans += w[u] - w[z];
    } else if (v != z) {
      ans += g[v];
      ans += w[v] - w[z];
    } else
      ans += g[z];
    print(ans, '\n');
  }
}

```