#include <bits/stdc++.h>
namespace IO {
char ch = '\n';
template <class T>
inline T ReadInt() {
  T x(0);
  bool f(1);
  while (ch < '0' || '9' < ch) {
    if (ch == '-') {
      f = 0;
    }
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return f ? x : -x;
}
template <class T>
inline T ReadUInt() {
  T x(0);
  while (ch < '0' || '9' < ch) {
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return x;
}
inline double ReadDouble() {
  long long int_num = ReadInt<long long>();
  if (ch == '.') {
    double pow10 = 1, result = int_num;
    ch = getchar();
    while ('0' <= ch && ch <= '9') {
      pow10 /= 10.0;
      result += pow10 * (ch ^ 48);
      ch = getchar();
    }
    return result;
  } else {
    return (double)int_num;
  }
}
inline void ReadT(int &x) { x = ReadInt<int>(); }
inline void ReadT(long long &x) { x = ReadInt<long long>(); }
inline void ReadT(bool &x) { x = ReadUInt<bool>(); }
inline void ReadT(unsigned int &x) { x = ReadUInt<unsigned int>(); }
inline void ReadT(unsigned long long &x) { x = ReadUInt<unsigned long long>(); }
inline void ReadT(double &x) { x = ReadDouble(); }
inline void ReadT(char &s) {
  for (; isspace(ch) && (~ch); ch = getchar())
    ;
  s = ch;
  ch = '\n';
}
inline void ReadT(char *s) {
  int len(0);
  for (; isspace(ch) && (~ch); ch = getchar())
    ;
  for (; !isspace(ch) && (~ch); ch = getchar()) {
    s[len++] = ch;
  }
  s[len] = '\0';
  ch = '\n';
}
template <typename T>
inline void Read(T &t) {
  ReadT(t);
}
template <typename T, typename... Args>
void Read(T &t, Args &...args) {
  ReadT(t);
  Read(args...);
}
template <typename T>
void WriteInt(T x) {
  if (x < 0) {
    printf("-");
    x = -x;
  }
  if (9 < x) {
    WriteInt(x / 10);
  }
  putchar(x % 10 + '0');
}
template <typename T>
void WriteUInt(T x) {
  if (9 < x) {
    WriteInt(x / 10);
  }
  putchar(x % 10 + '0');
}
void WriteDouble(long double x, int len) {
  WriteInt((long long)x);
  if (len) {
    x -= (int)x;
    putchar('.');
    if (!x) {
      while (len--) {
        putchar(48);
      }
      return;
    }
    while (len--) {
      x *= 10;
    }
    WriteInt((long long)round(x));
  }
}
template <typename T>
inline void WriteT(T x);
template <>
inline void WriteT<int>(int x) {
  WriteInt<int>(x);
}
template <>
inline void WriteT<long long>(long long x) {
  WriteInt<long long>(x);
}
template <>
inline void WriteT<bool>(bool x) {
  WriteUInt<bool>(x);
}
template <>
inline void WriteT<unsigned int>(unsigned int x) {
  WriteUInt<unsigned int>(x);
}
template <>
inline void WriteT<unsigned long long>(unsigned long long x) {
  WriteUInt<unsigned long long>(x);
}
template <>
inline void WriteT<double>(double x) {
  WriteDouble(x, 6);
}
template <>
inline void WriteT<char *>(char *s) {
  int len(strlen(s));
  while (len--) {
    putchar(*s++);
  }
}
template <>
inline void WriteT<const char *>(const char *s) {
  while (*s) {
    putchar(*s++);
  }
}
template <>
inline void WriteT<char>(char x) {
  putchar(x);
}
template <typename T>
inline void Write(T t) {
  WriteT(t);
}
template <typename T, typename... Args>
void Write(T t, Args... args) {
  WriteT(t);
  Write(args...);
}
template <typename T>
inline void Writeln(T t) {
  WriteT(t);
  puts("");
}
template <typename T, typename... Args>
inline void Writeln(T t, Args... args) {
  WriteT(t);
  Write(args...);
  puts("");
}
inline void Writeln() { puts(""); }
const char NUMBER[36] = {'0', '1', '2', '3', '4', '5', '6', '7', '8',
                         '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
                         'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q',
                         'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
template <typename T>
void WriteK(T x, int p) {
  if (x < 0) {
    printf("-");
    x = -x;
  }
  if (p <= x) {
    WriteK(x / p, p);
  }
  putchar(NUMBER[x % p]);
}
}  // namespace IO
using namespace IO;
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXM = MAXN << 1;
int n, m;
long long val[MAXN];
struct Edge {
  int to, next;
  long long val;
} edge[MAXM];
int edge_head[MAXN];
int edge_cnt = 0;
inline void AddEdge(int from, int to, long long val) {
  edge[++edge_cnt].to = to;
  edge[edge_cnt].val = val;
  edge[edge_cnt].next = edge_head[from];
  edge_head[from] = edge_cnt;
}
long long g[MAXN];
long long f[MAXN];
long long sumf[MAXN];
long long d[MAXN];
long long sumdec[MAXN];
long long tof[MAXN];
long long sump[MAXN], sume[MAXN];
int point_deep[MAXN];
int point_father[MAXN];
int point_son[MAXN];
int point_size[MAXN];
int chain_cnt = 0;
int point_id[MAXN];
int point_val[MAXN];
int chain_top[MAXN];
void DFS_1(int now = 1) {
  sump[now] = sump[point_father[now]] + val[now];
  int max_size = -1;
  point_size[now] = 1;
  for (int edge_i = edge_head[now]; edge_i; edge_i = edge[edge_i].next) {
    if (point_father[now] != edge[edge_i].to) {
      point_father[edge[edge_i].to] = now;
      point_deep[edge[edge_i].to] = point_deep[now] + 1;
      tof[edge[edge_i].to] = edge[edge_i].val;
      sume[edge[edge_i].to] = sume[now] + edge[edge_i].val;
      DFS_1(edge[edge_i].to);
      f[now] +=
          max(f[edge[edge_i].to] - 2 * edge[edge_i].val + val[edge[edge_i].to],
              0ll);
      point_size[now] += point_size[edge[edge_i].to];
      if (point_size[edge[edge_i].to] > max_size) {
        max_size = point_size[edge[edge_i].to];
        point_son[now] = edge[edge_i].to;
      }
    }
  }
  d[now] = max(f[now] - 2 * tof[now] + val[now], 0ll);
}
void DFS_2(int now = 1, int top = 1, long long on = 0) {
  g[now] = on;
  sumf[now] = sumf[point_father[now]] + f[now];
  sumdec[now] = sumdec[point_father[now]] + d[now];
  point_id[now] = ++chain_cnt;
  point_val[chain_cnt] = val[now];
  chain_top[now] = top;
  if (!point_son[now]) {
    return;
  }
  DFS_2(
      point_son[now], top,
      max(on + f[now] + val[now] - d[point_son[now]] - 2 * tof[point_son[now]],
          0ll));
  for (int edge_i = edge_head[now]; edge_i; edge_i = edge[edge_i].next) {
    if (edge[edge_i].to != point_father[now] &&
        edge[edge_i].to != point_son[now]) {
      DFS_2(edge[edge_i].to, edge[edge_i].to,
            max(on + f[now] + val[now] - d[edge[edge_i].to] -
                    2 * edge[edge_i].val,
                0ll));
    }
  }
}
inline int LCA(int u, int v) {
  while (chain_top[u] != chain_top[v]) {
    if (point_deep[chain_top[u]] < point_deep[chain_top[v]]) {
      swap(u, v);
    }
    u = point_father[chain_top[u]];
  }
  if (point_deep[v] < point_deep[u]) {
    swap(u, v);
  }
  return u;
}
long long Query(int u, int v) {
  int lca = LCA(u, v);
  return sumf[u] + sumf[v] - 2 * sumf[lca] + f[lca] - sumdec[u] - sumdec[v] +
         2 * sumdec[lca] + g[lca] - sume[u] - sume[v] + 2 * sume[lca] +
         sump[u] + sump[v] - sump[lca] - sump[point_father[lca]];
}
int main() {
  Read(n, m);
  for (int i = 1; i <= n; ++i) {
    Read(val[i]);
  }
  int u, v, w;
  for (int i = 1; i <= n - 1; ++i) {
    Read(u, v, w);
    AddEdge(u, v, w);
    AddEdge(v, u, w);
  }
  DFS_1();
  DFS_2();
  for (int i = 1; i <= m; ++i) {
    Read(u, v);
    Writeln(Query(u, v));
  }
  return 0;
}

### Prompt

Please formulate 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>
namespace IO {
char ch = '\n';
template <class T>
inline T ReadInt() {
  T x(0);
  bool f(1);
  while (ch < '0' || '9' < ch) {
    if (ch == '-') {
      f = 0;
    }
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return f ? x : -x;
}
template <class T>
inline T ReadUInt() {
  T x(0);
  while (ch < '0' || '9' < ch) {
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return x;
}
inline double ReadDouble() {
  long long int_num = ReadInt<long long>();
  if (ch == '.') {
    double pow10 = 1, result = int_num;
    ch = getchar();
    while ('0' <= ch && ch <= '9') {
      pow10 /= 10.0;
      result += pow10 * (ch ^ 48);
      ch = getchar();
    }
    return result;
  } else {
    return (double)int_num;
  }
}
inline void ReadT(int &x) { x = ReadInt<int>(); }
inline void ReadT(long long &x) { x = ReadInt<long long>(); }
inline void ReadT(bool &x) { x = ReadUInt<bool>(); }
inline void ReadT(unsigned int &x) { x = ReadUInt<unsigned int>(); }
inline void ReadT(unsigned long long &x) { x = ReadUInt<unsigned long long>(); }
inline void ReadT(double &x) { x = ReadDouble(); }
inline void ReadT(char &s) {
  for (; isspace(ch) && (~ch); ch = getchar())
    ;
  s = ch;
  ch = '\n';
}
inline void ReadT(char *s) {
  int len(0);
  for (; isspace(ch) && (~ch); ch = getchar())
    ;
  for (; !isspace(ch) && (~ch); ch = getchar()) {
    s[len++] = ch;
  }
  s[len] = '\0';
  ch = '\n';
}
template <typename T>
inline void Read(T &t) {
  ReadT(t);
}
template <typename T, typename... Args>
void Read(T &t, Args &...args) {
  ReadT(t);
  Read(args...);
}
template <typename T>
void WriteInt(T x) {
  if (x < 0) {
    printf("-");
    x = -x;
  }
  if (9 < x) {
    WriteInt(x / 10);
  }
  putchar(x % 10 + '0');
}
template <typename T>
void WriteUInt(T x) {
  if (9 < x) {
    WriteInt(x / 10);
  }
  putchar(x % 10 + '0');
}
void WriteDouble(long double x, int len) {
  WriteInt((long long)x);
  if (len) {
    x -= (int)x;
    putchar('.');
    if (!x) {
      while (len--) {
        putchar(48);
      }
      return;
    }
    while (len--) {
      x *= 10;
    }
    WriteInt((long long)round(x));
  }
}
template <typename T>
inline void WriteT(T x);
template <>
inline void WriteT<int>(int x) {
  WriteInt<int>(x);
}
template <>
inline void WriteT<long long>(long long x) {
  WriteInt<long long>(x);
}
template <>
inline void WriteT<bool>(bool x) {
  WriteUInt<bool>(x);
}
template <>
inline void WriteT<unsigned int>(unsigned int x) {
  WriteUInt<unsigned int>(x);
}
template <>
inline void WriteT<unsigned long long>(unsigned long long x) {
  WriteUInt<unsigned long long>(x);
}
template <>
inline void WriteT<double>(double x) {
  WriteDouble(x, 6);
}
template <>
inline void WriteT<char *>(char *s) {
  int len(strlen(s));
  while (len--) {
    putchar(*s++);
  }
}
template <>
inline void WriteT<const char *>(const char *s) {
  while (*s) {
    putchar(*s++);
  }
}
template <>
inline void WriteT<char>(char x) {
  putchar(x);
}
template <typename T>
inline void Write(T t) {
  WriteT(t);
}
template <typename T, typename... Args>
void Write(T t, Args... args) {
  WriteT(t);
  Write(args...);
}
template <typename T>
inline void Writeln(T t) {
  WriteT(t);
  puts("");
}
template <typename T, typename... Args>
inline void Writeln(T t, Args... args) {
  WriteT(t);
  Write(args...);
  puts("");
}
inline void Writeln() { puts(""); }
const char NUMBER[36] = {'0', '1', '2', '3', '4', '5', '6', '7', '8',
                         '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
                         'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q',
                         'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
template <typename T>
void WriteK(T x, int p) {
  if (x < 0) {
    printf("-");
    x = -x;
  }
  if (p <= x) {
    WriteK(x / p, p);
  }
  putchar(NUMBER[x % p]);
}
}  // namespace IO
using namespace IO;
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXM = MAXN << 1;
int n, m;
long long val[MAXN];
struct Edge {
  int to, next;
  long long val;
} edge[MAXM];
int edge_head[MAXN];
int edge_cnt = 0;
inline void AddEdge(int from, int to, long long val) {
  edge[++edge_cnt].to = to;
  edge[edge_cnt].val = val;
  edge[edge_cnt].next = edge_head[from];
  edge_head[from] = edge_cnt;
}
long long g[MAXN];
long long f[MAXN];
long long sumf[MAXN];
long long d[MAXN];
long long sumdec[MAXN];
long long tof[MAXN];
long long sump[MAXN], sume[MAXN];
int point_deep[MAXN];
int point_father[MAXN];
int point_son[MAXN];
int point_size[MAXN];
int chain_cnt = 0;
int point_id[MAXN];
int point_val[MAXN];
int chain_top[MAXN];
void DFS_1(int now = 1) {
  sump[now] = sump[point_father[now]] + val[now];
  int max_size = -1;
  point_size[now] = 1;
  for (int edge_i = edge_head[now]; edge_i; edge_i = edge[edge_i].next) {
    if (point_father[now] != edge[edge_i].to) {
      point_father[edge[edge_i].to] = now;
      point_deep[edge[edge_i].to] = point_deep[now] + 1;
      tof[edge[edge_i].to] = edge[edge_i].val;
      sume[edge[edge_i].to] = sume[now] + edge[edge_i].val;
      DFS_1(edge[edge_i].to);
      f[now] +=
          max(f[edge[edge_i].to] - 2 * edge[edge_i].val + val[edge[edge_i].to],
              0ll);
      point_size[now] += point_size[edge[edge_i].to];
      if (point_size[edge[edge_i].to] > max_size) {
        max_size = point_size[edge[edge_i].to];
        point_son[now] = edge[edge_i].to;
      }
    }
  }
  d[now] = max(f[now] - 2 * tof[now] + val[now], 0ll);
}
void DFS_2(int now = 1, int top = 1, long long on = 0) {
  g[now] = on;
  sumf[now] = sumf[point_father[now]] + f[now];
  sumdec[now] = sumdec[point_father[now]] + d[now];
  point_id[now] = ++chain_cnt;
  point_val[chain_cnt] = val[now];
  chain_top[now] = top;
  if (!point_son[now]) {
    return;
  }
  DFS_2(
      point_son[now], top,
      max(on + f[now] + val[now] - d[point_son[now]] - 2 * tof[point_son[now]],
          0ll));
  for (int edge_i = edge_head[now]; edge_i; edge_i = edge[edge_i].next) {
    if (edge[edge_i].to != point_father[now] &&
        edge[edge_i].to != point_son[now]) {
      DFS_2(edge[edge_i].to, edge[edge_i].to,
            max(on + f[now] + val[now] - d[edge[edge_i].to] -
                    2 * edge[edge_i].val,
                0ll));
    }
  }
}
inline int LCA(int u, int v) {
  while (chain_top[u] != chain_top[v]) {
    if (point_deep[chain_top[u]] < point_deep[chain_top[v]]) {
      swap(u, v);
    }
    u = point_father[chain_top[u]];
  }
  if (point_deep[v] < point_deep[u]) {
    swap(u, v);
  }
  return u;
}
long long Query(int u, int v) {
  int lca = LCA(u, v);
  return sumf[u] + sumf[v] - 2 * sumf[lca] + f[lca] - sumdec[u] - sumdec[v] +
         2 * sumdec[lca] + g[lca] - sume[u] - sume[v] + 2 * sume[lca] +
         sump[u] + sump[v] - sump[lca] - sump[point_father[lca]];
}
int main() {
  Read(n, m);
  for (int i = 1; i <= n; ++i) {
    Read(val[i]);
  }
  int u, v, w;
  for (int i = 1; i <= n - 1; ++i) {
    Read(u, v, w);
    AddEdge(u, v, w);
    AddEdge(v, u, w);
  }
  DFS_1();
  DFS_2();
  for (int i = 1; i <= m; ++i) {
    Read(u, v);
    Writeln(Query(u, v));
  }
  return 0;
}

```