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;
#define ll long long int
#define mkp make_pair
#define rep(i,s,f) for(i=s;i<f;i++)
#define db cout<<'h'<<'i'<<endl 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PI 3.14159265
#define mod 1000000007
#define mod2 998244353
#define space 100005
#define lg 18
//<<fixed << setprecision(9)
pii edge[space],foo[space],col[space];//count,length

int up[space][lg],in[space],out[space],tim,dist,ans[space];
vector<pii> G[space],query[space];

void dfs(int n,int p)
{
    in[n]=++tim;
    up[n][0]=p;
    int i;
    rep(i,1,lg)
    {
        up[n][i]=up[up[n][i-1]][i-1];
    }

    for(auto z:G[n])
    {
        if(z.F!=p)
        {
            dfs(z.F,n);
        }
    }
    out[n]=++tim;
}

void dfs2(int n,int p)
{
    for(auto x:query[n])
    {
        ans[x.F]+=(dist-col[foo[x.F].F].S+col[foo[x.F].F].F*foo[x.F].S)*x.S;
    }

    for(auto z:G[n])
    {
        if(z.F!=p)
        {
            dist+=edge[z.S].S;
            col[edge[z.S].F].F++;
            col[edge[z.S].F].S+=edge[z.S].S;
            dfs2(z.F,n);
            dist-=edge[z.S].S;
            col[edge[z.S].F].F--;
            col[edge[z.S].F].S-=edge[z.S].S;
        }
    }
}

bool anc(int a,int b)
{
    return in[a]<in[b] && out[a]>out[b];
}
int lca(int u,int v)
{
    for(int i=lg-1;i>=0;i--)
    {
        if(!anc(up[u][i],v))
        {
            u=up[u][i];
        }
    }
    return up[u][0];
}
int main()
{
    int n,i,j,t;
    boost;

    cin>>n>>t;
    int a,b,c,d;
    rep(i,0,n-1)
    {
        cin>>a>>b>>c>>d;
        edge[i]={c,d};
        G[a].pb({b,i});
        G[b].pb({a,i});
    }

    dfs(1,1);

    rep(i,1,t+1)
    {
        cin>>c>>d>>a>>b;
        foo[i]={c,d};
        if(anc(a,b))
        {
            query[a].pb({i,-1});
            query[b].pb({i,1});
        }
        else if(anc(b,a))
        {
            query[b].pb({i,-1});
            query[a].pb({i,1});
        }
        else
        {
            j=lca(a,b);
            query[j].pb({i,-2});
            query[a].pb({i,1});
            query[b].pb({i,1});
        }
    }
    dfs2(1,-1);

    rep(i,1,t+1) cout<<ans[i]<<'\n';
    return 0;
}