Problem: There is a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i, and the color and length of that edge are c_i and d_i, respectively. Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.

Answer the following Q queries:

* Query j (1 \leq j \leq Q): assuming that the length of every edge whose color is x_j is changed to y_j, find the distance between Vertex u_j and Vertex v_j. (The changes of the lengths of edges do not affect the subsequent queries.)

Constraints

* 2 \leq N \leq 10^5
* 1 \leq Q \leq 10^5
* 1 \leq a_i, b_i \leq N
* 1 \leq c_i \leq N-1
* 1 \leq d_i \leq 10^4
* 1 \leq x_j \leq N-1
* 1 \leq y_j \leq 10^4
* 1 \leq u_j < v_j \leq N
* The given graph is a tree.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
a_1 b_1 c_1 d_1
:
a_{N-1} b_{N-1} c_{N-1} d_{N-1}
x_1 y_1 u_1 v_1
:
x_Q y_Q u_Q v_Q


Output

Print Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to Query j.

Example

Input

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4


Output

130
200
60

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using PP = pair<int, int>;

struct Query {
  int a;
  int b;
  int c;
  int d;
  int m;
};

int N, Q;
vector<PP> G[100000];
int C[100000];
int D[100000];
Query V[100000];
vector<int> qs[100000];
int memo_dist[100000];
unordered_map<int, int> memo_cnt[100000];
unordered_map<int, int> memo_sum[100000];

int dep[100000];
int par[21][100000];
void pre_rec(int from, int prev, int d) {
  par[0][from] = prev;
  dep[from] = d;
  for (PP e : G[from]) {
    int to = e.first;
    if (to == prev) continue;
    pre_rec(to, from, d + 1);
  }
}

void pre() {
  pre_rec(0, -1, 0);
  for (int k = 0; k < 20; ++k) {
    for (int i = 0; i < N; ++i) {
      int p = par[k][i];
      par[k + 1][i] = p == -1 ? -1 : par[k][p];
    }
  }
}

int lca(int u, int v) {
  if (dep[u] > dep[v]) return lca(v, u);
  int diff = dep[v] - dep[u];
  for (int k = 20; k >= 0; --k) {
    if ((1 << k) <= diff) {
      v = par[k][v];
      diff -= (1 << k);
    }
  }
  if (u == v) return u;

  for (int k = 20; k >= 0; --k) {
    if (par[k][u] != par[k][v]) {
      u = par[k][u];
      v = par[k][v];
    }
  }
  return par[0][u];
}

int cnt[100000];
int sum[100000];
void rec(int from, int prev, int dist) {
  memo_dist[from] = dist;
  for (int q : qs[from]) {
    memo_cnt[from][q] = cnt[q];
    memo_sum[from][q] = sum[q];
  }
  
  for (PP e : G[from]) {
    int to = e.first;
    int idx = e.second;
    if (to == prev) continue;
    int c = C[idx];
    int d = D[idx];
    ++cnt[c];
    sum[c] += d;
    rec(to, from, dist + d);
    sum[c] -= d;
    --cnt[c];
  }
}

long val(int v, int c, int d) {
  return memo_dist[v] - memo_sum[v][c] + d * memo_cnt[v][c];
}

int main() {
  cin >> N >> Q;
  for (int i = 0; i < N - 1; ++i) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    --a; --b; --c;
    G[a].push_back(PP(b, i));
    G[b].push_back(PP(a, i));
    C[i] = c;
    D[i] = d;
  }
  
  for (int k = 0; k < Q; ++k) {
    int a, b, c, d;
    cin >> c >> d >> a >> b;
    --a; --b; --c;
    V[k] = Query{ a, b, c, d, 0 };
  }
  
  pre();
  
  for (int k = 0; k < Q; ++k) {
    int a = V[k].a;
    int b = V[k].b;
    int m = lca(a, b);
    V[k].m = m;
    int c = V[k].c;
    qs[a].push_back(c);
    qs[b].push_back(c);
    qs[m].push_back(c);
  }
  
  rec(0, -1, 0);
  
  for (int k = 0; k < Q; ++k) {
    int a = V[k].a;
    int b = V[k].b;
    int c = V[k].c;
    int d = V[k].d;
    int m = V[k].m;
    long ans = val(a, c, d) + val(b, c, d) - 2 * val(m, c, d);
    cout << ans << endl;
  }
}