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. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int INF = 2e9;
const long long INFLL = 1e18;
const int MAX_N = 300000;
const int MAX_K = 20;
int N, Q;
long long cost[MAX_N + 1];
vector<pair<int, int> > gp[MAX_N + 1];
long long dp1[MAX_N + 1], dp2[MAX_N + 1][MAX_K + 1], dp3[MAX_N + 1];
long long c2[MAX_N + 1];
int up[MAX_N + 1][MAX_K + 1], lv[MAX_N + 1], p[MAX_N + 1];
void dfs(int x) {
  up[x][0] = p[x];
  for (int i = 1; i < MAX_K; i++) {
    up[x][i] = up[up[x][i - 1]][i - 1];
  }
  dp1[x] += cost[x];
  for (pair<int, int> i : gp[x]) {
    if (i.first == p[x]) continue;
    p[i.first] = x;
    c2[i.first] = (long long)i.second;
    lv[i.first] = lv[x] + 1;
    dfs(i.first);
    dp1[x] += max(0LL, dp1[i.first] - (long long)i.second * 2LL);
  }
}
void dfs2(int x) {
  int y = x;
  dp2[x][0] = dp1[x] - c2[x];
  for (int i = 1; i < MAX_K; i++) {
    dp2[x][i] = dp2[x][i - 1] + dp2[p[y]][i - 1] -
                max(0LL, dp1[y] - (long long)c2[y] * 2LL);
    y = up[y][i - 1];
  }
  for (pair<int, int> i : gp[x]) {
    if (i.first == p[x]) continue;
    dp3[i.first] =
        max(0LL, dp1[x] + dp3[x] -
                     max(0LL, dp1[i.first] - (long long)i.second * 2LL) -
                     (long long)i.second * 2LL);
    dfs2(i.first);
  }
}
int lca(int x, int y) {
  for (int i = MAX_K - 1; i >= 0; i--) {
    if (lv[up[x][i]] >= lv[y]) {
      x = up[x][i];
    }
    if (lv[up[y][i]] >= lv[x]) {
      y = up[y][i];
    }
  }
  if (x == y) return x;
  for (int i = MAX_K - 1; i >= 0; i--) {
    if (up[x][i] != up[y][i]) {
      x = up[x][i];
      y = up[y][i];
    }
  }
  return up[x][0];
}
long long calc(int x, int y) {
  long long ret = 0;
  int z = -1;
  for (int i = MAX_K - 1; i >= 0; i--) {
    if (lv[up[x][i]] >= lv[y]) {
      ret += dp2[x][i];
      if (z == -1) {
        z = x;
        for (int j = 0; j < i; j++) z = up[z][j];
      } else {
        z = up[z][i];
      }
      ret -= max(0LL, dp1[z] - (long long)c2[z] * 2LL);
      x = up[x][i];
    }
  }
  return ret;
}
int main() {
  scanf("%d%d", &N, &Q);
  for (int i = 1; i <= N; i++) {
    scanf("%lld", &cost[i]);
  }
  for (int i = 1; i < N; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    gp[a].push_back({b, c});
    gp[b].push_back({a, c});
  }
  lv[1] = 1;
  dfs(1);
  dfs2(1);
  for (int i = 1; i <= N; i++) {
  }
  for (int i = 1; i <= Q; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    int l = lca(a, b);
    printf("%lld\n", calc(a, l) + calc(b, l) + dp1[l] + dp3[l]);
  }
  return 0;
}