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;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
vector<pipii> g[100005];
LL ans[100005];

int par[17][100005], depth[100005];
LL dp[100005];
void dfs(int u, int p, int d, LL val){
    depth[u] = d;
    par[0][u] = p;
    dp[u] = val;
    for(int i=0;i<g[u].size();i++){
        int v = g[u][i].first, c = g[u][i].second.first, l = g[u][i].second.second;
        if(v == p) continue;
        dfs(v, u, d+1, val+l);
    }
}
int LCA(int a, int b){
    if(depth[b] > depth[a]) swap(a, b);
    int diff = depth[a] - depth[b];
    for(int i=17-1;i>=0;i--){
        if((diff>>i)&1) a = par[i][a];
    }
    if(a == b) return a;
    for(int i=17-1;i>=0;i--){
        if(par[i][a] != par[i][b]) a = par[i][a], b = par[i][b];
    }
    return par[0][a];
}

LL dist(int a, int b){
    return dp[a] + dp[b] - 2*dp[LCA(a, b)];
}

vector<pipii> cur[100005];
LL dis[100005], cnt[100005];
void dfs2(int u, int p){

    for(int i=0;i<cur[u].size();i++){
        int j = cur[u][i].first, x = cur[u][i].second.first, y = cur[u][i].second.second;

        if(j < 0){
            j = -j;
            ans[j] -= 2*(y*1ll*cnt[x] - dis[x]);
        }
        else{
            ans[j] += y*1ll*cnt[x] - dis[x];
        }
    }

    for(int i=0;i<g[u].size();i++){
        int v = g[u][i].first, c = g[u][i].second.first, d = g[u][i].second.second;
        if(v == p) continue;

        dis[c] += d;
        cnt[c]++;
        dfs2(v, u);
        dis[c] -= d;
        cnt[c]--;
    }
}


int main(){
    int n, q, a, b, c, d;
    scanf("%d%d", &n, &q);
    for(int i=1;i<=n-1;i++){
        scanf("%d%d%d%d", &a, &b, &c, &d);
        g[a].push_back(pipii(b, pii(c, d)));
        g[b].push_back(pipii(a, pii(c, d)));
    }   
    dfs(1, 0, 0, 0);
    for(int j=1;j<17;j++){
        for(int i=1;i<=n;i++){
            if(par[j-1][i] != 0) par[j][i] = par[j-1][par[j-1][i]];
        }
    }
    for(int i=1;i<=q;i++){
        int x, y, u, v, lca;
        scanf("%d%d%d%d", &x, &y, &u, &v);
        lca = LCA(u, v);
        ans[i] = dist(u, v);

        cur[lca].push_back(pipii(-i, pii(x, y)));
        cur[u].push_back(pipii(i, pii(x, y)));
        cur[v].push_back(pipii(i, pii(x, y)));
    }
    dfs2(1, 0);
    for(int i=1;i<=q;i++) printf("%lld\n", ans[i]);
}