#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const long long infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;
const int maxn = 3e5 + 5, maxjump = 19;
int n_nodes, n_edges, nq;
vector<int> adj[maxn];
int depth[maxn] = {0};
long long inverse_dp[maxn] = {0}, subtree_dp[maxn] = {0}, root_dp[maxn] = {0};
int vals[maxn];
vector<array<int, 3>> edges;
map<int, int> edge_wt[maxn];
int par[maxn];
struct lca {
  int n, tl;
  vector<int> t;
  vector<int> first;
  vector<int> euler;
  vector<int> dv;
  void init(int N) {
    n = N;
    euler.clear();
    euler.reserve(2 * n);
    first.clear();
    first.resize(n);
    dv.clear();
    dv.resize(n);
    dv[0] = 0;
    dfs(0, 0);
    tl = euler.size();
    t.clear();
    t.resize(tl << 2, -1);
    build(1, 0, tl - 1);
  }
  int get_lca(int u, int v) {
    int l = first[u], r = first[v];
    if (l > r) swap(l, r);
    return query(1, 0, tl - 1, l, r);
  }
  void dfs(int node, int parent) {
    first[node] = euler.size();
    euler.push_back(node);
    for (int next : adj[node]) {
      if (next == parent) continue;
      dv[next] = dv[node] + 1;
      dfs(next, node);
      euler.push_back(node);
    }
  }
  int task(int child1, int child2) {
    if (child1 == -1) return child2;
    if (child2 == -1) return child1;
    if (dv[child1] < dv[child2]) {
      return child1;
    } else {
      return child2;
    }
  }
  void build(int node, int l, int r) {
    if (l == r) {
      t[node] = euler[l];
    } else {
      int mid = (l + r) >> 1;
      build(node << 1, l, mid);
      build((node << 1) + 1, mid + 1, r);
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  int query(int node, int l, int r, int lq, int rq) {
    if (lq > rq) {
      return -1;
    } else if (lq <= l && rq >= r) {
      return t[node];
    } else {
      int mid = (l + r) >> 1;
      return task(query(node << 1, l, mid, lq, min(rq, mid)),
                  query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
    }
  }
};
lca lca;
struct binlift {
  int n, jump;
  vector<vector<int>> parent_table;
  vector<int> logtable;
  vector<vector<long long>> data;
  void init(int N, int JUMP) {
    n = N;
    jump = JUMP;
    parent_table = vector<vector<int>>(n, vector<int>(jump, -1));
    data = vector<vector<long long>>(n, vector<long long>(jump, 0));
    logtable = vector<int>(n + 1, 0);
    for (int i = 2; i < n + 1; i++) {
      logtable[i] = logtable[i >> 1] + 1;
    }
  }
  void add_node(int v, int p) {
    parent_table[v][0] = v;
    data[v][0] = subtree_dp[v] - inverse_dp[v] - edge_wt[v][par[v]];
    parent_table[v][1] = p;
    data[v][1] =
        data[v][0] + subtree_dp[p] - inverse_dp[p] - edge_wt[p][par[p]];
  }
  void build() {
    for (int j = 2; j < jump; j++) {
      for (int v = 0; v < n; v++) {
        if (parent_table[v][j - 1] != -1 &&
            parent_table[parent_table[v][j - 1]][1] != -1) {
          parent_table[v][j] =
              parent_table[parent_table[parent_table[v][j - 1]][1]][j - 1];
          data[v][j] = data[v][j - 1] +
                       data[parent_table[parent_table[v][j - 1]][1]][j - 1];
        } else {
          parent_table[v][j] = -1;
        }
      }
    }
  }
  long long lift(int v, int dist) {
    if (dist == 0) {
      return 0;
    }
    int opt = logtable[dist];
    return data[v][opt] +
           lift(parent_table[parent_table[v][opt]][1], dist - (1 << opt));
  }
  int lift_ancestor(int v, int dist) {
    if (dist == 1) {
      return v;
    }
    int opt = logtable[dist];
    if (dist == (1 << opt)) {
      return parent_table[v][opt];
    }
    return lift_ancestor(parent_table[parent_table[v][opt]][1],
                         dist - (1 << opt));
  }
};
binlift b;
void terraform(int v, int p, long long temp) {
  for (int u : adj[v]) {
    if (u == p) continue;
    long long T = temp - inverse_dp[u];
    root_dp[u] += max(0LL, T - 2 * edge_wt[u][v]);
    terraform(u, v, root_dp[u]);
  }
}
void dfs(int v, int p) {
  subtree_dp[v] = vals[v];
  for (int u : adj[v]) {
    if (u == p) continue;
    par[u] = v;
    depth[u] = depth[v] + 1;
    dfs(u, v);
    inverse_dp[u] = max(0LL, subtree_dp[u] - 2 * edge_wt[u][v]);
    subtree_dp[v] += inverse_dp[u];
  }
  root_dp[v] = subtree_dp[v];
}
void add_dfs(int v, int p) {
  for (int u : adj[v]) {
    if (u == p) continue;
    b.add_node(u, v);
    add_dfs(u, v);
  }
}
void solve() {
  cin >> n_nodes >> nq;
  n_edges = n_nodes - 1;
  for (int i = 0; i < n_nodes; i++) {
    cin >> vals[i];
  }
  for (int i = 0; i < n_edges; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
    edges.push_back({u, v, w});
    edge_wt[u][v] = w;
    edge_wt[v][u] = w;
  }
  b.init(n_nodes, maxjump);
  dfs(0, 0);
  terraform(0, 0, root_dp[0]);
  add_dfs(0, 0);
  b.build();
  lca.init(n_nodes);
  for (int q = 0; q < nq; q++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    int LCA = lca.get_lca(u, v);
    long long ans = 0;
    if (u != LCA) {
      int inbw = depth[u] - depth[LCA];
      ans += b.lift(u, inbw);
    }
    if (v != LCA) {
      int inbw = depth[v] - depth[LCA];
      ans += b.lift(v, inbw);
    }
    ans += root_dp[LCA];
    cout << ans << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int q = 1;
  while (q-- > 0) {
    solve();
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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 mod = 1000000007;
const long long infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;
const int maxn = 3e5 + 5, maxjump = 19;
int n_nodes, n_edges, nq;
vector<int> adj[maxn];
int depth[maxn] = {0};
long long inverse_dp[maxn] = {0}, subtree_dp[maxn] = {0}, root_dp[maxn] = {0};
int vals[maxn];
vector<array<int, 3>> edges;
map<int, int> edge_wt[maxn];
int par[maxn];
struct lca {
  int n, tl;
  vector<int> t;
  vector<int> first;
  vector<int> euler;
  vector<int> dv;
  void init(int N) {
    n = N;
    euler.clear();
    euler.reserve(2 * n);
    first.clear();
    first.resize(n);
    dv.clear();
    dv.resize(n);
    dv[0] = 0;
    dfs(0, 0);
    tl = euler.size();
    t.clear();
    t.resize(tl << 2, -1);
    build(1, 0, tl - 1);
  }
  int get_lca(int u, int v) {
    int l = first[u], r = first[v];
    if (l > r) swap(l, r);
    return query(1, 0, tl - 1, l, r);
  }
  void dfs(int node, int parent) {
    first[node] = euler.size();
    euler.push_back(node);
    for (int next : adj[node]) {
      if (next == parent) continue;
      dv[next] = dv[node] + 1;
      dfs(next, node);
      euler.push_back(node);
    }
  }
  int task(int child1, int child2) {
    if (child1 == -1) return child2;
    if (child2 == -1) return child1;
    if (dv[child1] < dv[child2]) {
      return child1;
    } else {
      return child2;
    }
  }
  void build(int node, int l, int r) {
    if (l == r) {
      t[node] = euler[l];
    } else {
      int mid = (l + r) >> 1;
      build(node << 1, l, mid);
      build((node << 1) + 1, mid + 1, r);
      t[node] = task(t[node << 1], t[(node << 1) + 1]);
    }
  }
  int query(int node, int l, int r, int lq, int rq) {
    if (lq > rq) {
      return -1;
    } else if (lq <= l && rq >= r) {
      return t[node];
    } else {
      int mid = (l + r) >> 1;
      return task(query(node << 1, l, mid, lq, min(rq, mid)),
                  query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
    }
  }
};
lca lca;
struct binlift {
  int n, jump;
  vector<vector<int>> parent_table;
  vector<int> logtable;
  vector<vector<long long>> data;
  void init(int N, int JUMP) {
    n = N;
    jump = JUMP;
    parent_table = vector<vector<int>>(n, vector<int>(jump, -1));
    data = vector<vector<long long>>(n, vector<long long>(jump, 0));
    logtable = vector<int>(n + 1, 0);
    for (int i = 2; i < n + 1; i++) {
      logtable[i] = logtable[i >> 1] + 1;
    }
  }
  void add_node(int v, int p) {
    parent_table[v][0] = v;
    data[v][0] = subtree_dp[v] - inverse_dp[v] - edge_wt[v][par[v]];
    parent_table[v][1] = p;
    data[v][1] =
        data[v][0] + subtree_dp[p] - inverse_dp[p] - edge_wt[p][par[p]];
  }
  void build() {
    for (int j = 2; j < jump; j++) {
      for (int v = 0; v < n; v++) {
        if (parent_table[v][j - 1] != -1 &&
            parent_table[parent_table[v][j - 1]][1] != -1) {
          parent_table[v][j] =
              parent_table[parent_table[parent_table[v][j - 1]][1]][j - 1];
          data[v][j] = data[v][j - 1] +
                       data[parent_table[parent_table[v][j - 1]][1]][j - 1];
        } else {
          parent_table[v][j] = -1;
        }
      }
    }
  }
  long long lift(int v, int dist) {
    if (dist == 0) {
      return 0;
    }
    int opt = logtable[dist];
    return data[v][opt] +
           lift(parent_table[parent_table[v][opt]][1], dist - (1 << opt));
  }
  int lift_ancestor(int v, int dist) {
    if (dist == 1) {
      return v;
    }
    int opt = logtable[dist];
    if (dist == (1 << opt)) {
      return parent_table[v][opt];
    }
    return lift_ancestor(parent_table[parent_table[v][opt]][1],
                         dist - (1 << opt));
  }
};
binlift b;
void terraform(int v, int p, long long temp) {
  for (int u : adj[v]) {
    if (u == p) continue;
    long long T = temp - inverse_dp[u];
    root_dp[u] += max(0LL, T - 2 * edge_wt[u][v]);
    terraform(u, v, root_dp[u]);
  }
}
void dfs(int v, int p) {
  subtree_dp[v] = vals[v];
  for (int u : adj[v]) {
    if (u == p) continue;
    par[u] = v;
    depth[u] = depth[v] + 1;
    dfs(u, v);
    inverse_dp[u] = max(0LL, subtree_dp[u] - 2 * edge_wt[u][v]);
    subtree_dp[v] += inverse_dp[u];
  }
  root_dp[v] = subtree_dp[v];
}
void add_dfs(int v, int p) {
  for (int u : adj[v]) {
    if (u == p) continue;
    b.add_node(u, v);
    add_dfs(u, v);
  }
}
void solve() {
  cin >> n_nodes >> nq;
  n_edges = n_nodes - 1;
  for (int i = 0; i < n_nodes; i++) {
    cin >> vals[i];
  }
  for (int i = 0; i < n_edges; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
    edges.push_back({u, v, w});
    edge_wt[u][v] = w;
    edge_wt[v][u] = w;
  }
  b.init(n_nodes, maxjump);
  dfs(0, 0);
  terraform(0, 0, root_dp[0]);
  add_dfs(0, 0);
  b.build();
  lca.init(n_nodes);
  for (int q = 0; q < nq; q++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    int LCA = lca.get_lca(u, v);
    long long ans = 0;
    if (u != LCA) {
      int inbw = depth[u] - depth[LCA];
      ans += b.lift(u, inbw);
    }
    if (v != LCA) {
      int inbw = depth[v] - depth[LCA];
      ans += b.lift(v, inbw);
    }
    ans += root_dp[LCA];
    cout << ans << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int q = 1;
  while (q-- > 0) {
    solve();
  }
  return 0;
}

```