#include <bits/stdc++.h>
using namespace std;
const int N = 100009;
const int LOG = 17;
int P[N][LOG], T[N], L[N], subsz[N], chain[N], spe_ch[N], eu[N], x[N], y[N],
    chain_id = 0, pos[N], f[N];
vector<pair<int, int> > edge[N];
vector<int> e[N], l[N], r[N], seg[N];
vector<pair<int, int> > Qu;
void process3(int n) {
  int i, j;
  memset(P, -1, sizeof(P));
  for (i = 1; i <= n; i++) P[i][0] = T[i];
  for (j = 1; (1 << j) <= n; j++) {
    for (i = 1; i <= n; i++) {
      if (P[i][j - 1] != -1) {
        P[i][j] = P[P[i][j - 1]][j - 1];
      }
    }
  }
}
int LCA(int p, int q) {
  int tmp, log, i;
  if (L[p] < L[q]) {
    tmp = p, p = q, q = tmp;
  }
  for (log = 1; 1 << log <= L[p]; log++)
    ;
  log--;
  for (i = log; i >= 0; i--) {
    if (L[p] - (1 << i) >= L[q]) {
      p = P[p][i];
    }
    if (p == q) return p;
  }
  for (i = log; i >= 0; i--) {
    if (P[p][i] != -1 && P[p][i] != P[q][i]) {
      p = P[p][i], q = P[q][i];
    }
  }
  return T[p];
}
int dfs(int vertex, int parent, int depth) {
  L[vertex] = depth;
  T[vertex] = parent;
  int mx_sz = 0;
  subsz[vertex] = 1;
  for (int i = 0; i < edge[vertex].size(); ++i) {
    if (edge[vertex][i].first != parent) {
      subsz[vertex] += dfs(edge[vertex][i].first, vertex, depth + 1);
      eu[edge[vertex][i].first] = edge[vertex][i].second;
      if (subsz[edge[vertex][i].first] > mx_sz) {
        spe_ch[vertex] = edge[vertex][i].first;
        mx_sz = subsz[spe_ch[vertex]];
      }
    }
  }
  return subsz[vertex];
}
void make_chains(int vertex, int parent, int tok) {
  if (!tok) {
    chain[vertex] = ++chain_id;
    e[chain_id].push_back(-1);
  } else
    chain[vertex] = tok;
  e[chain[vertex]].push_back(vertex);
  pos[vertex] = e[chain[vertex]].size() - 1;
  for (int i = 0; i < edge[vertex].size(); ++i) {
    if (edge[vertex][i].first != parent) {
      if (spe_ch[vertex] == edge[vertex][i].first) {
        make_chains(spe_ch[vertex], vertex, chain[vertex]);
      } else
        make_chains(edge[vertex][i].first, vertex, 0);
    }
  }
}
void update(int n, int it, int fn, int ch_id, int q) {
  if (it == fn) {
    l[ch_id][n] = r[ch_id][n] = 1;
    seg[ch_id][n] = f[1];
    return;
  }
  int m = (it + fn) / 2, ln = n * 2, rn;
  rn = ln + 1;
  if (q <= m)
    update(ln, it, m, ch_id, q);
  else
    update(rn, m + 1, fn, ch_id, q);
  seg[ch_id][n] = seg[ch_id][ln] + seg[ch_id][rn];
  if (r[ch_id][rn] > 0 && l[ch_id][ln] > 0) {
    seg[ch_id][n] -= f[r[ch_id][rn]] + f[l[ch_id][ln]];
    seg[ch_id][n] += f[r[ch_id][rn] + l[ch_id][ln]];
    if (l[ch_id][rn] < fn - m)
      l[ch_id][n] = l[ch_id][rn];
    else
      l[ch_id][n] = fn - m + l[ch_id][ln];
    if (r[ch_id][ln] < m - it + 1)
      r[ch_id][n] = r[ch_id][ln];
    else
      r[ch_id][n] = m - it + 1 + r[ch_id][rn];
  } else {
    l[ch_id][n] = l[ch_id][rn];
    r[ch_id][n] = r[ch_id][ln];
  }
}
void live_edge(int bot_v) {
  int chn = chain[bot_v], sz;
  sz = e[chn].size() - 1;
  update(1, 1, sz, chn, pos[bot_v]);
}
int LCA2(int v, int u) {
  for (int i = LOG; i >= 0; i--) {
    if (L[v] - (1 << i) > L[u]) {
      v = P[v][i];
    }
  }
  return v;
}
pair<int, pair<int, int> > query(int n, int it, int fn, int q1, int q2,
                                 int ch_id) {
  if (it == q1 && fn == q2) {
    return make_pair(seg[ch_id][n], make_pair(l[ch_id][n], r[ch_id][n]));
  }
  int m = (it + fn) / 2;
  if (q2 <= m)
    return query(n * 2, it, m, q1, q2, ch_id);
  else if (q1 > m)
    return query(n * 2 + 1, m + 1, fn, q1, q2, ch_id);
  else {
    pair<int, pair<int, int> > tmp1 = query(n * 2, it, m, q1, m, ch_id);
    pair<int, pair<int, int> > tmp2 =
        query(n * 2 + 1, m + 1, fn, m + 1, q2, ch_id);
    pair<int, pair<int, int> > tmp;
    tmp.first = tmp1.first + tmp2.first;
    if (tmp1.second.first > 0 && tmp2.second.second > 0) {
      tmp.first -= f[tmp1.second.first] + f[tmp2.second.second];
      tmp.first += f[tmp1.second.first + tmp2.second.second];
      if (tmp2.second.first == q2 - m) {
        tmp.second.first = tmp2.second.first + tmp1.second.first;
      } else
        tmp.second.first = tmp2.second.first;
      if (tmp1.second.second == m - q1 + 1)
        tmp.second.second = tmp1.second.second + tmp2.second.second;
      else
        tmp.second.second = tmp1.second.second;
    } else {
      tmp.second.first = tmp2.second.first;
      tmp.second.second = tmp1.second.second;
    }
    return tmp;
  }
}
pair<int, pair<int, int> > moveup(int u, int v) {
  int ch_id = chain[u], sz;
  sz = e[ch_id].size() - 1;
  if (chain[u] == chain[v]) return query(1, 1, sz, pos[v], pos[u], ch_id);
  pair<int, pair<int, int> > tmp1 = moveup(T[e[ch_id][1]], v);
  pair<int, pair<int, int> > tmp2 = query(1, 1, sz, 1, pos[u], ch_id);
  pair<int, pair<int, int> > tmp;
  tmp.first = tmp1.first + tmp2.first;
  if (tmp1.second.first > 0 && tmp2.second.second > 0) {
    tmp.first -= f[tmp1.second.first] + f[tmp2.second.second];
    tmp.first += f[tmp1.second.first + tmp2.second.second];
    if (tmp1.second.second == L[T[e[ch_id][1]]] - L[v] + 1) {
      tmp.second.second = tmp1.second.second + tmp2.second.second;
    } else
      tmp.second.second = tmp1.second.second;
    if (tmp2.second.first == pos[u])
      tmp.second.first = tmp2.second.first + tmp1.second.first;
    else
      tmp.second.first = tmp2.second.first;
  } else {
    tmp.second.first = tmp2.second.first;
    tmp.second.second = tmp1.second.second;
  }
  return tmp;
}
int geta(int u, int v) {
  int lca = LCA(u, v);
  if (lca != u && lca != v) {
    int lca1 = LCA2(u, lca);
    int lca2 = LCA2(v, lca);
    pair<int, pair<int, int> > tmp1 = moveup(u, lca1);
    pair<int, pair<int, int> > tmp2 = moveup(v, lca2);
    pair<int, pair<int, int> > tmp;
    tmp.first = tmp1.first + tmp2.first;
    if (tmp1.second.second > 0 && tmp2.second.second > 0) {
      tmp.first -= f[tmp1.second.second] + f[tmp2.second.second];
      tmp.first += f[tmp1.second.second + tmp2.second.second];
    }
    return tmp.first;
  } else if (lca == u) {
    int lca1 = LCA2(v, lca);
    pair<int, pair<int, int> > tmp = moveup(v, lca1);
    return tmp.first;
  } else {
    int lca1 = LCA2(u, lca);
    pair<int, pair<int, int> > tmp = moveup(u, lca1);
    return tmp.first;
  }
}
int main() {
  int n, Q, u, v, w;
  cin >> n >> Q;
  for (int i = 1; i < n; ++i) cin >> f[i];
  for (int i = 1; i < n; ++i) {
    cin >> u >> v >> w;
    edge[u].push_back(make_pair(v, w));
    edge[v].push_back(make_pair(u, w));
  }
  int L;
  Qu.push_back(make_pair(0, 0));
  for (int i = 1; i <= Q; ++i) {
    cin >> x[i] >> y[i] >> L;
    Qu.push_back(make_pair(L, i));
  }
  sort(Qu.begin() + 1, Qu.end());
  dfs(1, -1, 0);
  make_chains(1, -1, 0);
  process3(n);
  vector<pair<int, int> > o;
  o.push_back(make_pair(0, 0));
  for (int i = 2; i <= n; ++i) {
    o.push_back(make_pair(eu[i], i));
  }
  sort(o.begin() + 1, o.end());
  for (int i = 1; i <= chain_id; ++i) {
    seg[i].resize(4 * e[i].size());
    l[i].resize(seg[i].size());
    r[i].resize(l[i].size());
    fill(seg[i].begin(), seg[i].end(), 0);
    fill(l[i].begin(), l[i].end(), 0);
    fill(r[i].begin(), r[i].end(), 0);
  }
  pair<int, int> tmp;
  int pt = n - 1;
  int ans[N];
  for (int i = Q; i >= 1; i--) {
    tmp = Qu[i];
    while (pt > 0 && o[pt].first >= tmp.first) {
      live_edge(o[pt].second);
      pt--;
    }
    ans[tmp.second] = geta(x[tmp.second], y[tmp.second]);
  }
  for (int i = 1; i <= Q; ++i) cout << ans[i] << endl;
  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>
using namespace std;
const int N = 100009;
const int LOG = 17;
int P[N][LOG], T[N], L[N], subsz[N], chain[N], spe_ch[N], eu[N], x[N], y[N],
    chain_id = 0, pos[N], f[N];
vector<pair<int, int> > edge[N];
vector<int> e[N], l[N], r[N], seg[N];
vector<pair<int, int> > Qu;
void process3(int n) {
  int i, j;
  memset(P, -1, sizeof(P));
  for (i = 1; i <= n; i++) P[i][0] = T[i];
  for (j = 1; (1 << j) <= n; j++) {
    for (i = 1; i <= n; i++) {
      if (P[i][j - 1] != -1) {
        P[i][j] = P[P[i][j - 1]][j - 1];
      }
    }
  }
}
int LCA(int p, int q) {
  int tmp, log, i;
  if (L[p] < L[q]) {
    tmp = p, p = q, q = tmp;
  }
  for (log = 1; 1 << log <= L[p]; log++)
    ;
  log--;
  for (i = log; i >= 0; i--) {
    if (L[p] - (1 << i) >= L[q]) {
      p = P[p][i];
    }
    if (p == q) return p;
  }
  for (i = log; i >= 0; i--) {
    if (P[p][i] != -1 && P[p][i] != P[q][i]) {
      p = P[p][i], q = P[q][i];
    }
  }
  return T[p];
}
int dfs(int vertex, int parent, int depth) {
  L[vertex] = depth;
  T[vertex] = parent;
  int mx_sz = 0;
  subsz[vertex] = 1;
  for (int i = 0; i < edge[vertex].size(); ++i) {
    if (edge[vertex][i].first != parent) {
      subsz[vertex] += dfs(edge[vertex][i].first, vertex, depth + 1);
      eu[edge[vertex][i].first] = edge[vertex][i].second;
      if (subsz[edge[vertex][i].first] > mx_sz) {
        spe_ch[vertex] = edge[vertex][i].first;
        mx_sz = subsz[spe_ch[vertex]];
      }
    }
  }
  return subsz[vertex];
}
void make_chains(int vertex, int parent, int tok) {
  if (!tok) {
    chain[vertex] = ++chain_id;
    e[chain_id].push_back(-1);
  } else
    chain[vertex] = tok;
  e[chain[vertex]].push_back(vertex);
  pos[vertex] = e[chain[vertex]].size() - 1;
  for (int i = 0; i < edge[vertex].size(); ++i) {
    if (edge[vertex][i].first != parent) {
      if (spe_ch[vertex] == edge[vertex][i].first) {
        make_chains(spe_ch[vertex], vertex, chain[vertex]);
      } else
        make_chains(edge[vertex][i].first, vertex, 0);
    }
  }
}
void update(int n, int it, int fn, int ch_id, int q) {
  if (it == fn) {
    l[ch_id][n] = r[ch_id][n] = 1;
    seg[ch_id][n] = f[1];
    return;
  }
  int m = (it + fn) / 2, ln = n * 2, rn;
  rn = ln + 1;
  if (q <= m)
    update(ln, it, m, ch_id, q);
  else
    update(rn, m + 1, fn, ch_id, q);
  seg[ch_id][n] = seg[ch_id][ln] + seg[ch_id][rn];
  if (r[ch_id][rn] > 0 && l[ch_id][ln] > 0) {
    seg[ch_id][n] -= f[r[ch_id][rn]] + f[l[ch_id][ln]];
    seg[ch_id][n] += f[r[ch_id][rn] + l[ch_id][ln]];
    if (l[ch_id][rn] < fn - m)
      l[ch_id][n] = l[ch_id][rn];
    else
      l[ch_id][n] = fn - m + l[ch_id][ln];
    if (r[ch_id][ln] < m - it + 1)
      r[ch_id][n] = r[ch_id][ln];
    else
      r[ch_id][n] = m - it + 1 + r[ch_id][rn];
  } else {
    l[ch_id][n] = l[ch_id][rn];
    r[ch_id][n] = r[ch_id][ln];
  }
}
void live_edge(int bot_v) {
  int chn = chain[bot_v], sz;
  sz = e[chn].size() - 1;
  update(1, 1, sz, chn, pos[bot_v]);
}
int LCA2(int v, int u) {
  for (int i = LOG; i >= 0; i--) {
    if (L[v] - (1 << i) > L[u]) {
      v = P[v][i];
    }
  }
  return v;
}
pair<int, pair<int, int> > query(int n, int it, int fn, int q1, int q2,
                                 int ch_id) {
  if (it == q1 && fn == q2) {
    return make_pair(seg[ch_id][n], make_pair(l[ch_id][n], r[ch_id][n]));
  }
  int m = (it + fn) / 2;
  if (q2 <= m)
    return query(n * 2, it, m, q1, q2, ch_id);
  else if (q1 > m)
    return query(n * 2 + 1, m + 1, fn, q1, q2, ch_id);
  else {
    pair<int, pair<int, int> > tmp1 = query(n * 2, it, m, q1, m, ch_id);
    pair<int, pair<int, int> > tmp2 =
        query(n * 2 + 1, m + 1, fn, m + 1, q2, ch_id);
    pair<int, pair<int, int> > tmp;
    tmp.first = tmp1.first + tmp2.first;
    if (tmp1.second.first > 0 && tmp2.second.second > 0) {
      tmp.first -= f[tmp1.second.first] + f[tmp2.second.second];
      tmp.first += f[tmp1.second.first + tmp2.second.second];
      if (tmp2.second.first == q2 - m) {
        tmp.second.first = tmp2.second.first + tmp1.second.first;
      } else
        tmp.second.first = tmp2.second.first;
      if (tmp1.second.second == m - q1 + 1)
        tmp.second.second = tmp1.second.second + tmp2.second.second;
      else
        tmp.second.second = tmp1.second.second;
    } else {
      tmp.second.first = tmp2.second.first;
      tmp.second.second = tmp1.second.second;
    }
    return tmp;
  }
}
pair<int, pair<int, int> > moveup(int u, int v) {
  int ch_id = chain[u], sz;
  sz = e[ch_id].size() - 1;
  if (chain[u] == chain[v]) return query(1, 1, sz, pos[v], pos[u], ch_id);
  pair<int, pair<int, int> > tmp1 = moveup(T[e[ch_id][1]], v);
  pair<int, pair<int, int> > tmp2 = query(1, 1, sz, 1, pos[u], ch_id);
  pair<int, pair<int, int> > tmp;
  tmp.first = tmp1.first + tmp2.first;
  if (tmp1.second.first > 0 && tmp2.second.second > 0) {
    tmp.first -= f[tmp1.second.first] + f[tmp2.second.second];
    tmp.first += f[tmp1.second.first + tmp2.second.second];
    if (tmp1.second.second == L[T[e[ch_id][1]]] - L[v] + 1) {
      tmp.second.second = tmp1.second.second + tmp2.second.second;
    } else
      tmp.second.second = tmp1.second.second;
    if (tmp2.second.first == pos[u])
      tmp.second.first = tmp2.second.first + tmp1.second.first;
    else
      tmp.second.first = tmp2.second.first;
  } else {
    tmp.second.first = tmp2.second.first;
    tmp.second.second = tmp1.second.second;
  }
  return tmp;
}
int geta(int u, int v) {
  int lca = LCA(u, v);
  if (lca != u && lca != v) {
    int lca1 = LCA2(u, lca);
    int lca2 = LCA2(v, lca);
    pair<int, pair<int, int> > tmp1 = moveup(u, lca1);
    pair<int, pair<int, int> > tmp2 = moveup(v, lca2);
    pair<int, pair<int, int> > tmp;
    tmp.first = tmp1.first + tmp2.first;
    if (tmp1.second.second > 0 && tmp2.second.second > 0) {
      tmp.first -= f[tmp1.second.second] + f[tmp2.second.second];
      tmp.first += f[tmp1.second.second + tmp2.second.second];
    }
    return tmp.first;
  } else if (lca == u) {
    int lca1 = LCA2(v, lca);
    pair<int, pair<int, int> > tmp = moveup(v, lca1);
    return tmp.first;
  } else {
    int lca1 = LCA2(u, lca);
    pair<int, pair<int, int> > tmp = moveup(u, lca1);
    return tmp.first;
  }
}
int main() {
  int n, Q, u, v, w;
  cin >> n >> Q;
  for (int i = 1; i < n; ++i) cin >> f[i];
  for (int i = 1; i < n; ++i) {
    cin >> u >> v >> w;
    edge[u].push_back(make_pair(v, w));
    edge[v].push_back(make_pair(u, w));
  }
  int L;
  Qu.push_back(make_pair(0, 0));
  for (int i = 1; i <= Q; ++i) {
    cin >> x[i] >> y[i] >> L;
    Qu.push_back(make_pair(L, i));
  }
  sort(Qu.begin() + 1, Qu.end());
  dfs(1, -1, 0);
  make_chains(1, -1, 0);
  process3(n);
  vector<pair<int, int> > o;
  o.push_back(make_pair(0, 0));
  for (int i = 2; i <= n; ++i) {
    o.push_back(make_pair(eu[i], i));
  }
  sort(o.begin() + 1, o.end());
  for (int i = 1; i <= chain_id; ++i) {
    seg[i].resize(4 * e[i].size());
    l[i].resize(seg[i].size());
    r[i].resize(l[i].size());
    fill(seg[i].begin(), seg[i].end(), 0);
    fill(l[i].begin(), l[i].end(), 0);
    fill(r[i].begin(), r[i].end(), 0);
  }
  pair<int, int> tmp;
  int pt = n - 1;
  int ans[N];
  for (int i = Q; i >= 1; i--) {
    tmp = Qu[i];
    while (pt > 0 && o[pt].first >= tmp.first) {
      live_edge(o[pt].second);
      pt--;
    }
    ans[tmp.second] = geta(x[tmp.second], y[tmp.second]);
  }
  for (int i = 1; i <= Q; ++i) cout << ans[i] << endl;
  return 0;
}

```