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<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

const int max_n = 100000+10;

typedef struct M {
    int to;
    int color;
    int dist;
}node;

int N,q;
int par[max_n][20];
vector<node> V[max_n];
vector<node> Q[max_n];
int ans[max_n];
int h[max_n];
int de[max_n];
int c[max_n];
int co[max_n];

void get(int p) {
    h[p] = h[par[p][0]]+1;
    for(auto u: V[p]) {
        if(u.to != par[p][0]) {
            par[u.to][0] = p;
            de[u.to] = de[p]+u.dist;
            get(u.to);
        }
    }
}

int lca(int x,int y) {
    if(h[x] > h[y])
        swap(x,y);
    int t = h[y]-h[x];
    for(int i = 0;i < 18;i++) {
        if(t&(1<<i))
            y = par[y][i];
    }
    if(x == y)
        return x;
    for(int i = 17;i >= 0;i--) {
        if(par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }

    return par[x][0];
}

void dfs(int p) {
    for(auto u: Q[p]) {
        if(u.to > 0) {
            ans[u.to] += de[p]+c[u.color]*u.dist-co[u.color];
        } else {
            ans[-u.to] -= 2*(de[p]+c[u.color]*u.dist - co[u.color]);
        }
    }

    for(auto u:V[p]) {
        if(u.to == par[p][0])
            continue;
        c[u.color]++;
        co[u.color] += u.dist;
        dfs(u.to);
        c[u.color]--;
        co[u.color]-=u.dist;
    }

    return;
}

int main(void) {
    cin>>N>>q;

    for(int i = 1;i < N;i++) {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        V[a].push_back({b,c,d});
        V[b].push_back({a,c,d});
    }

    get(1);
    for(int i = 1;i <= 17;i++) {
        for(int j = 1;j <= N;j++) {
            par[j][i] = par[par[j][i-1]][i-1];
        }
    }

    for(int i = 1;i <= q;i++) {
        int x,y,u,v;
        cin>>x>>y>>u>>v;
        Q[u].push_back({i, x, y});
        Q[v].push_back({i, x, y});
        Q[lca(u,v)].push_back({-i, x, y});
    }
    dfs(1);
    for(int i = 1;i <= q;i++) {
        cout<<ans[i]<<endl;
    }

    return 0;
}