#include <bits/stdc++.h>
#pragma comment(linker, '/STACK:200000')
using namespace std;
class Tree {
 public:
  bool dfsProcessed;
  int n, lg;
  vector<vector<int> > adj;
  vector<vector<int> > lca;
  vector<int> in, out, h, sz;
  int dc;
  Tree(){};
  Tree(int _n) {
    n = _n;
    lg = log2(n) + 1;
    adj.resize(n);
    lca.resize(n, vector<int>(lg));
    h.resize(n);
    in.resize(n);
    out.resize(n);
    sz.resize(n);
    dc = 0;
    dfsProcessed = false;
  }
  void addEdge(int x, int y) {
    adj[x].emplace_back(y);
    adj[y].emplace_back(x);
  }
  void dfs(int x, int ult) {
    sz[x] = 1;
    lca[x][0] = ult;
    in[x] = dc++;
    for (int i = 1; i < lg; ++i) lca[x][i] = lca[lca[x][i - 1]][i - 1];
    for (int y : adj[x]) {
      if (y == ult) continue;
      h[y] = h[x] + 1;
      dfs(y, x);
      sz[x] += sz[y];
    }
    out[x] = dc++;
  }
  int getLca(int x, int y) {
    if (h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    for (int i = lg - 1; i >= 0; --i)
      if ((d >> i) & 1) x = lca[x][i];
    if (x == y) return x;
    for (int i = lg - 1; i >= 0; --i)
      if (lca[x][i] != lca[y][i]) {
        x = lca[x][i];
        y = lca[y][i];
      }
    return lca[x][0];
  }
  int getDad(int x) { return lca[x][0]; }
  int getDist(int x, int y) { return h[x] + h[y] - 2 * h[getLca(x, y)]; }
  void process() {
    if (dfsProcessed) return;
    dfsProcessed = true;
    dfs(0, 0);
  }
};
template <typename T>
class Segtree {
 private:
  vector<T> tr;
  int n;
  void build(int no, int l, int r) {
    tr[no] = T();
    if (l == r) {
      tr[no] = T(0, 0, 0, 1);
      return;
    }
    int nxt = (no << 1), mid = (l + r) >> 1;
    build(nxt, l, mid);
    build(nxt + 1, mid + 1, r);
    tr[no] = tr[nxt] + tr[nxt + 1];
  }
  T query(int no, int l, int r, int i, int j) {
    if (r < i || l > j) return T();
    if (l >= i && r <= j) return tr[no];
    int nxt = (no << 1), mid = (l + r) >> 1;
    return query(nxt, l, mid, i, j) + query(nxt + 1, mid + 1, r, i, j);
  }
  void pointUpdate(int no, int l, int r, int i, T nw) {
    if (l == r) {
      tr[no] = nw;
      return;
    }
    int nxt = (no << 1), mid = (l + r) >> 1;
    if (i <= mid)
      pointUpdate(nxt, l, mid, i, nw);
    else
      pointUpdate(nxt + 1, mid + 1, r, i, nw);
    tr[no] = tr[nxt] + tr[nxt + 1];
  }

 public:
  Segtree(){};
  Segtree(int _n) {
    n = _n;
    tr.resize(n * 4);
    build(1, 0, n - 1);
  }
  T query(int l, int r) { return query(1, 0, n - 1, l, r); }
  void update(int i, T nw) { pointUpdate(1, 0, n - 1, i, nw); }
};
template <typename T>
class HLD {
 public:
  int n;
  Tree t;
  vector<int> chain, posInBase, chainHead;
  Segtree<T> st;
  int bc, cc;
  HLD(Tree _t) {
    t = _t;
    n = t.n;
    t.process();
    st = Segtree<T>(n + 1);
    chainHead.resize(n + 1);
    posInBase.resize(n + 1);
    chain.resize(n + 1);
    chainHead[0] = 0;
    bc = cc = 0;
    dfs(0, 0);
  }
  void dfs(int x, int ult) {
    chain[x] = cc;
    posInBase[x] = bc++;
    int idx = -1, bst = -1;
    for (int y : t.adj[x]) {
      if (y == ult) continue;
      if (t.sz[y] > bst) {
        bst = t.sz[y];
        idx = y;
      }
    }
    if (idx != -1) dfs(idx, x);
    for (int y : t.adj[x]) {
      if (y == ult || y == idx) continue;
      cc++;
      chainHead[cc] = y;
      dfs(y, x);
    }
  }
  T getLca(int lca, int x) {
    T s;
    while (chain[lca] != chain[x]) {
      int c = chain[x];
      T ax = st.query(posInBase[chainHead[c]], posInBase[x]);
      s = ax + s;
      x = t.getDad(chainHead[c]);
    }
    if (x == lca) return s;
    T ax = st.query(posInBase[lca] + 1, posInBase[x]);
    s = ax + s;
    return s;
  }
  T getPath(int x, int y) {
    int L = t.getLca(x, y);
    T a = getLca(L, x);
    T b = getLca(L, y);
    swap(a.pref, a.suff);
    return a + b;
  }
  void activateEdge(int x, int y, T v) {
    if (t.getDad(x) == y)
      st.update(posInBase[x], v);
    else
      st.update(posInBase[y], v);
  }
};
const int N = 200010;
int n, q;
int f[N];
struct Node {
  int pref, suff, ans, len;
  Node() { pref = suff = ans = len = 0; };
  Node(int _pref, int _suff, int _ans, int _len) {
    pref = _pref;
    suff = _suff;
    ans = _ans;
    len = _len;
  }
  Node operator+(Node other) const {
    Node sol;
    sol.ans = ans + other.ans - f[suff] - f[other.pref] + f[suff + other.pref];
    sol.len = len + other.len;
    sol.pref = pref;
    if (pref == len) sol.pref += other.pref;
    sol.suff = other.suff;
    if (other.suff == other.len) sol.suff += suff;
    return sol;
  }
};
struct Edge {
  int x, y, w;
  Edge(){};
  void read() {
    scanf("%d %d %d", &x, &y, &w);
    x--;
    y--;
  }
  bool operator<(Edge o) const { return w < o.w; }
};
struct Query {
  int x, y, l, id;
  Query(){};
  void read(int _id) {
    scanf("%d %d %d", &x, &y, &l);
    x--;
    y--;
    id = _id;
  }
  bool operator<(Query o) const { return l < o.l; }
};
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i < n; ++i) scanf("%d", f + i);
  vector<Edge> ed(n - 1);
  Tree g(n);
  for (int i = 0; i + 1 < n; ++i) {
    ed[i].read();
    g.addEdge(ed[i].x, ed[i].y);
  }
  sort(ed.rbegin(), ed.rend());
  vector<Query> que(q);
  for (int i = 0; i < q; ++i) que[i].read(i);
  sort(que.rbegin(), que.rend());
  HLD<Node> hld(g);
  vector<int> sol(q);
  int j = 0;
  for (int i = 0; i < q; ++i) {
    while (j < ed.size() && que[i].l <= ed[j].w) {
      hld.activateEdge(ed[j].x, ed[j].y, Node(1, 1, f[1], 1));
      j++;
    }
    sol[que[i].id] = hld.getPath(que[i].x, que[i].y).ans;
  }
  for (int i : sol) printf("%d\n", i);
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

Tavas lives in Tavaspolis. Tavaspolis has n cities numbered from 1 to n connected by n - 1 bidirectional roads. There exists a path between any two cities. Also each road has a length.

<image>

Tavas' favorite strings are binary strings (they contain only 0 and 1). For any binary string like s = s1s2... sk, T(s) is its Goodness. T(s) can be calculated as follows:

Consider there are exactly m blocks of 1s in this string (a block of 1s in s is a maximal consecutive substring of s that only contains 1) with lengths x1, x2, ..., xm.

Define <image> where f is a given sequence (if m = 0, then T(s) = 0).

Tavas loves queries. He asks you to answer q queries. In each query he gives you numbers v, u, l and you should print following number:

Consider the roads on the path from city v to city u: e1, e2, ..., ex.

Build the binary string b of length x such that: bi = 1 if and only if l ≤ w(ei) where w(e) is the length of road e.

You should print T(b) for this query.

Input

The first line of input contains integers n and q (2 ≤ n ≤ 105 and 1 ≤ q ≤ 105).

The next line contains n - 1 space separated integers f1, f2, ..., fn - 1 (|fi| ≤ 1000).

The next n - 1 lines contain the details of the roads. Each line contains integers v, u and w and it means that there's a road between cities v and u of length w (1 ≤ v, u ≤ n and 1 ≤ w ≤ 109).

The next q lines contain the details of the queries. Each line contains integers v, u, l (1 ≤ v, u ≤ n, v ≠ u and 1 ≤ l ≤ 109).

Output

Print the answer of each query in a single line.

Examples

Input

2 3
10
1 2 3
1 2 2
1 2 3
1 2 4


Output

10
10
0


Input

6 6
-5 0 0 2 10
1 2 1
2 3 2
3 4 5
4 5 1
5 6 5
1 6 1
1 6 2
1 6 5
3 6 5
4 6 4
1 4 2


Output

10
-5
-10
-10
-5
0

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, '/STACK:200000')
using namespace std;
class Tree {
 public:
  bool dfsProcessed;
  int n, lg;
  vector<vector<int> > adj;
  vector<vector<int> > lca;
  vector<int> in, out, h, sz;
  int dc;
  Tree(){};
  Tree(int _n) {
    n = _n;
    lg = log2(n) + 1;
    adj.resize(n);
    lca.resize(n, vector<int>(lg));
    h.resize(n);
    in.resize(n);
    out.resize(n);
    sz.resize(n);
    dc = 0;
    dfsProcessed = false;
  }
  void addEdge(int x, int y) {
    adj[x].emplace_back(y);
    adj[y].emplace_back(x);
  }
  void dfs(int x, int ult) {
    sz[x] = 1;
    lca[x][0] = ult;
    in[x] = dc++;
    for (int i = 1; i < lg; ++i) lca[x][i] = lca[lca[x][i - 1]][i - 1];
    for (int y : adj[x]) {
      if (y == ult) continue;
      h[y] = h[x] + 1;
      dfs(y, x);
      sz[x] += sz[y];
    }
    out[x] = dc++;
  }
  int getLca(int x, int y) {
    if (h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    for (int i = lg - 1; i >= 0; --i)
      if ((d >> i) & 1) x = lca[x][i];
    if (x == y) return x;
    for (int i = lg - 1; i >= 0; --i)
      if (lca[x][i] != lca[y][i]) {
        x = lca[x][i];
        y = lca[y][i];
      }
    return lca[x][0];
  }
  int getDad(int x) { return lca[x][0]; }
  int getDist(int x, int y) { return h[x] + h[y] - 2 * h[getLca(x, y)]; }
  void process() {
    if (dfsProcessed) return;
    dfsProcessed = true;
    dfs(0, 0);
  }
};
template <typename T>
class Segtree {
 private:
  vector<T> tr;
  int n;
  void build(int no, int l, int r) {
    tr[no] = T();
    if (l == r) {
      tr[no] = T(0, 0, 0, 1);
      return;
    }
    int nxt = (no << 1), mid = (l + r) >> 1;
    build(nxt, l, mid);
    build(nxt + 1, mid + 1, r);
    tr[no] = tr[nxt] + tr[nxt + 1];
  }
  T query(int no, int l, int r, int i, int j) {
    if (r < i || l > j) return T();
    if (l >= i && r <= j) return tr[no];
    int nxt = (no << 1), mid = (l + r) >> 1;
    return query(nxt, l, mid, i, j) + query(nxt + 1, mid + 1, r, i, j);
  }
  void pointUpdate(int no, int l, int r, int i, T nw) {
    if (l == r) {
      tr[no] = nw;
      return;
    }
    int nxt = (no << 1), mid = (l + r) >> 1;
    if (i <= mid)
      pointUpdate(nxt, l, mid, i, nw);
    else
      pointUpdate(nxt + 1, mid + 1, r, i, nw);
    tr[no] = tr[nxt] + tr[nxt + 1];
  }

 public:
  Segtree(){};
  Segtree(int _n) {
    n = _n;
    tr.resize(n * 4);
    build(1, 0, n - 1);
  }
  T query(int l, int r) { return query(1, 0, n - 1, l, r); }
  void update(int i, T nw) { pointUpdate(1, 0, n - 1, i, nw); }
};
template <typename T>
class HLD {
 public:
  int n;
  Tree t;
  vector<int> chain, posInBase, chainHead;
  Segtree<T> st;
  int bc, cc;
  HLD(Tree _t) {
    t = _t;
    n = t.n;
    t.process();
    st = Segtree<T>(n + 1);
    chainHead.resize(n + 1);
    posInBase.resize(n + 1);
    chain.resize(n + 1);
    chainHead[0] = 0;
    bc = cc = 0;
    dfs(0, 0);
  }
  void dfs(int x, int ult) {
    chain[x] = cc;
    posInBase[x] = bc++;
    int idx = -1, bst = -1;
    for (int y : t.adj[x]) {
      if (y == ult) continue;
      if (t.sz[y] > bst) {
        bst = t.sz[y];
        idx = y;
      }
    }
    if (idx != -1) dfs(idx, x);
    for (int y : t.adj[x]) {
      if (y == ult || y == idx) continue;
      cc++;
      chainHead[cc] = y;
      dfs(y, x);
    }
  }
  T getLca(int lca, int x) {
    T s;
    while (chain[lca] != chain[x]) {
      int c = chain[x];
      T ax = st.query(posInBase[chainHead[c]], posInBase[x]);
      s = ax + s;
      x = t.getDad(chainHead[c]);
    }
    if (x == lca) return s;
    T ax = st.query(posInBase[lca] + 1, posInBase[x]);
    s = ax + s;
    return s;
  }
  T getPath(int x, int y) {
    int L = t.getLca(x, y);
    T a = getLca(L, x);
    T b = getLca(L, y);
    swap(a.pref, a.suff);
    return a + b;
  }
  void activateEdge(int x, int y, T v) {
    if (t.getDad(x) == y)
      st.update(posInBase[x], v);
    else
      st.update(posInBase[y], v);
  }
};
const int N = 200010;
int n, q;
int f[N];
struct Node {
  int pref, suff, ans, len;
  Node() { pref = suff = ans = len = 0; };
  Node(int _pref, int _suff, int _ans, int _len) {
    pref = _pref;
    suff = _suff;
    ans = _ans;
    len = _len;
  }
  Node operator+(Node other) const {
    Node sol;
    sol.ans = ans + other.ans - f[suff] - f[other.pref] + f[suff + other.pref];
    sol.len = len + other.len;
    sol.pref = pref;
    if (pref == len) sol.pref += other.pref;
    sol.suff = other.suff;
    if (other.suff == other.len) sol.suff += suff;
    return sol;
  }
};
struct Edge {
  int x, y, w;
  Edge(){};
  void read() {
    scanf("%d %d %d", &x, &y, &w);
    x--;
    y--;
  }
  bool operator<(Edge o) const { return w < o.w; }
};
struct Query {
  int x, y, l, id;
  Query(){};
  void read(int _id) {
    scanf("%d %d %d", &x, &y, &l);
    x--;
    y--;
    id = _id;
  }
  bool operator<(Query o) const { return l < o.l; }
};
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i < n; ++i) scanf("%d", f + i);
  vector<Edge> ed(n - 1);
  Tree g(n);
  for (int i = 0; i + 1 < n; ++i) {
    ed[i].read();
    g.addEdge(ed[i].x, ed[i].y);
  }
  sort(ed.rbegin(), ed.rend());
  vector<Query> que(q);
  for (int i = 0; i < q; ++i) que[i].read(i);
  sort(que.rbegin(), que.rend());
  HLD<Node> hld(g);
  vector<int> sol(q);
  int j = 0;
  for (int i = 0; i < q; ++i) {
    while (j < ed.size() && que[i].l <= ed[j].w) {
      hld.activateEdge(ed[j].x, ed[j].y, Node(1, 1, f[1], 1));
      j++;
    }
    sol[que[i].id] = hld.getPath(que[i].x, que[i].y).ans;
  }
  for (int i : sol) printf("%d\n", i);
  return 0;
}

```