#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
const char lf = '\n';
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline int ty() {
  int a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace ae86
using ae86::ty;
const int _ = 300007, __ = _ << 1, lglg = 20;
vector<pair<int, long long>> e[_];
inline void adde(int a, int b, long long c) { e[a].emplace_back(b, c); }
inline void addde(int a, int b, long long c) { adde(a, b, c), adde(b, a, c); }
int n, qn;
long long val[_] = {0};
int fa[_] = {0}, dep[_] = {0}, pfa[lglg + 1][_] = {0};
long long sval[_] = {0}, xdep[_] = {0};
void dfs(int x, int ff) {
  fa[x] = ff, dep[x] = dep[ff] + 1, sval[x] = sval[ff] + val[x];
  for (auto [b, c] : e[x])
    if (b != ff) xdep[b] = xdep[x] + c, dfs(b, x);
}
int lca(int a, int b, int &aa, int &bb) {
  if (dep[a] < dep[b]) swap(a, b);
  for (int i = lglg; i >= 0; i--)
    if (dep[pfa[i][a]] >= dep[b]) a = pfa[i][a];
  if (a == b) return a;
  for (int i = lglg; i >= 0; i--)
    if (pfa[i][a] != pfa[i][b]) a = pfa[i][a], b = pfa[i][b];
  aa = a, bb = b;
  return fa[a];
}
long long f[_] = {0}, cf[_] = {0};
void dfs2(int x) {
  cf[x] = 0;
  for (auto [b, c] : e[x])
    if (b != fa[x])
      dfs2(b), f[b] = max(cf[b] + val[b] - c - c, 0), cf[x] += f[b];
}
long long uf[_] = {0}, sw[_] = {0};
void dfs3(int x, long long v, long long w) {
  uf[x] = v, sw[x] = w;
  for (auto [b, c] : e[x])
    if (b != fa[x])
      dfs3(b, max(v + val[x] + cf[x] - f[b] - c - c, 0),
           max(w + cf[x] - f[b], 0));
}
long long finder(int a, int b) {
  if (dep[a] > dep[b]) swap(a, b);
  int aa, bb;
  int c = lca(a, b, aa, bb);
  if (a == c) {
    if (b == c) return cf[a] + uf[a] + val[a];
    long long ans = sval[b] - sval[a] + val[a];
    ans -= xdep[b] - xdep[a], ans += sw[b] - sw[a], ans += uf[a] + cf[b];
    return ans;
  }
  long long ans = sval[a] + sval[b] - sval[c] * 2 + val[c];
  ans -= xdep[a] + xdep[b] - xdep[c] * 2,
      ans += sw[a] + sw[b] - sw[aa] - sw[bb];
  ans += cf[c] - f[aa] - f[bb], ans += uf[c] + cf[a] + cf[b];
  return ans;
}
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  n = ty(), qn = ty();
  for (int i = 1; i <= n; i++) val[i] = ty();
  for (int i = 1, a, b, c; i < n; i++)
    a = ty(), b = ty(), c = ty(), addde(a, b, c);
  dfs(1, 0), dfs2(1), dfs3(1, 0, 0);
  for (int i = 1; i <= n; i++) pfa[0][i] = fa[i];
  for (int i = 1; i <= lglg; i++)
    for (int j = 1; j <= n; j++) pfa[i][j] = pfa[i - 1][pfa[i - 1][j]];
  for (int qq = 1; qq <= qn; qq++) {
    int a = ty(), b = ty();
    cout << finder(a, b) << lf;
  }
  return 0;
}

### 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 <typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
const char lf = '\n';
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline int ty() {
  int a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace ae86
using ae86::ty;
const int _ = 300007, __ = _ << 1, lglg = 20;
vector<pair<int, long long>> e[_];
inline void adde(int a, int b, long long c) { e[a].emplace_back(b, c); }
inline void addde(int a, int b, long long c) { adde(a, b, c), adde(b, a, c); }
int n, qn;
long long val[_] = {0};
int fa[_] = {0}, dep[_] = {0}, pfa[lglg + 1][_] = {0};
long long sval[_] = {0}, xdep[_] = {0};
void dfs(int x, int ff) {
  fa[x] = ff, dep[x] = dep[ff] + 1, sval[x] = sval[ff] + val[x];
  for (auto [b, c] : e[x])
    if (b != ff) xdep[b] = xdep[x] + c, dfs(b, x);
}
int lca(int a, int b, int &aa, int &bb) {
  if (dep[a] < dep[b]) swap(a, b);
  for (int i = lglg; i >= 0; i--)
    if (dep[pfa[i][a]] >= dep[b]) a = pfa[i][a];
  if (a == b) return a;
  for (int i = lglg; i >= 0; i--)
    if (pfa[i][a] != pfa[i][b]) a = pfa[i][a], b = pfa[i][b];
  aa = a, bb = b;
  return fa[a];
}
long long f[_] = {0}, cf[_] = {0};
void dfs2(int x) {
  cf[x] = 0;
  for (auto [b, c] : e[x])
    if (b != fa[x])
      dfs2(b), f[b] = max(cf[b] + val[b] - c - c, 0), cf[x] += f[b];
}
long long uf[_] = {0}, sw[_] = {0};
void dfs3(int x, long long v, long long w) {
  uf[x] = v, sw[x] = w;
  for (auto [b, c] : e[x])
    if (b != fa[x])
      dfs3(b, max(v + val[x] + cf[x] - f[b] - c - c, 0),
           max(w + cf[x] - f[b], 0));
}
long long finder(int a, int b) {
  if (dep[a] > dep[b]) swap(a, b);
  int aa, bb;
  int c = lca(a, b, aa, bb);
  if (a == c) {
    if (b == c) return cf[a] + uf[a] + val[a];
    long long ans = sval[b] - sval[a] + val[a];
    ans -= xdep[b] - xdep[a], ans += sw[b] - sw[a], ans += uf[a] + cf[b];
    return ans;
  }
  long long ans = sval[a] + sval[b] - sval[c] * 2 + val[c];
  ans -= xdep[a] + xdep[b] - xdep[c] * 2,
      ans += sw[a] + sw[b] - sw[aa] - sw[bb];
  ans += cf[c] - f[aa] - f[bb], ans += uf[c] + cf[a] + cf[b];
  return ans;
}
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  n = ty(), qn = ty();
  for (int i = 1; i <= n; i++) val[i] = ty();
  for (int i = 1, a, b, c; i < n; i++)
    a = ty(), b = ty(), c = ty(), addde(a, b, c);
  dfs(1, 0), dfs2(1), dfs3(1, 0, 0);
  for (int i = 1; i <= n; i++) pfa[0][i] = fa[i];
  for (int i = 1; i <= lglg; i++)
    for (int j = 1; j <= n; j++) pfa[i][j] = pfa[i - 1][pfa[i - 1][j]];
  for (int qq = 1; qq <= qn; qq++) {
    int a = ty(), b = ty();
    cout << finder(a, b) << lf;
  }
  return 0;
}

```