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;

typedef long long ll;

const int lg = 21;

int n, q;
int d[100100];
int up[100100][22];
int col[100100];
ll cost[100100];
ll ans[100100];
int cnt[100100];
ll col_dist[100100];
vector<int> adj[100100];
vector<ll> weight[100100];
vector<int> color[100100];
vector<int> query[100100];

int lca(int u, int v) {
    if (d[u] > d[v]) swap(u, v);

    int delta = d[v] - d[u];
    for (int i = 0; i <= lg; i++) {
        if (delta & (1 << i)){
            v = up[v][i];
        }
    }

    if (u == v) return u;

    for (int i = lg; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

void dfs(int v, int p, int depth) {
    d[v] = depth;
    up[v][0] = p;
    for (int i = 1; i <= lg; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (int i = 0; i < (int)adj[v].size(); i++) {
        if (adj[v][i] == p) continue;
        dfs(adj[v][i], v, depth + 1);
    }
}

void solve(int v, int p, ll dist) {
    for (int idx: query[v]) {
        ll mul = 1;
        if (idx < 0)  {
            mul = -2;
            idx = -idx;
        }
        ans[idx] += mul * (cnt[col[idx]] * cost[idx] - col_dist[col[idx]] + dist);
    }

    for (int i = 0; i < (int)adj[v].size(); i++) {
        if (adj[v][i] == p) continue;
        cnt[color[v][i]]++;
        col_dist[color[v][i]] += weight[v][i];
        solve(adj[v][i], v, dist + weight[v][i]);
        cnt[color[v][i]]--;
        col_dist[color[v][i]] -= weight[v][i];
    }
}



int main() {
    scanf("%d %d", &n, &q);

    for (int i = 0; i < n - 1; i++) {
        int u, v, c;
        ll w;
        scanf("%d %d %d %lld", &u, &v, &c, &w);
        adj[u].push_back(v);
        adj[v].push_back(u);
        color[u].push_back(c);
        color[v].push_back(c);
        weight[u].push_back(w);
        weight[v].push_back(w);
    }

    dfs(1, 0, 0);
    // for (int j = 1; j <= lg; j++) {
    //     for (int i = 1; i <= n; i++) {
    //         up[i][j] = up[up[i - 1][j - 1]][j - 1];
    //     }
    // }

    for (int i = 1; i <= q; i++) {
        int u, v;
        scanf("%d %lld %d %d", &col[i], &cost[i], &u, &v);
        query[u].push_back(i);
        query[v].push_back(i);
        query[lca(u, v)].push_back(-i);
        // printf("LCA %d\n", lca(u, v));
    }

    solve(1, 0, 0);

    for (int i = 1; i <= q; i++) {
        printf("%lld\n", ans[i]);
    }
}