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<cstdio>
#include<vector>
using namespace std;
int to[200001],nex[200001],val[200001],col[200001],st[100001];
int fa[100001],son[100001],top[100001],dep[100001],siz[100001],sum[100001];
int ans[100001],colsum[100001],colnum[100001];
int n,m,cnt;
vector<int>c1[100001],c2[100001],id[100001],imp[100001];
void addedge(int x,int y,int v,int color)
{
    to[++cnt]=y;
    val[cnt]=v;
    col[cnt]=color;
    nex[cnt]=st[x];
    st[x]=cnt;
}
void dfs1(int x)
{
    dep[x]=dep[fa[x]]+1;
    siz[x]=1;
    for(int i=st[x];i;i=nex[i])
    {
        if(to[i]==fa[x])continue;
        fa[to[i]]=x;
        sum[to[i]]=sum[x]+val[i];
        dfs1(to[i]);
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[son[x]])son[x]=to[i];
    }
}
void dfs2(int x,int f)
{
    top[x]=f;
    if(son[x])dfs2(son[x],f);
    for(int i=st[x];i;i=nex[i])
    {
        if(to[i]==son[x]||to[i]==fa[x])continue;
        dfs2(to[i],to[i]);
    }
}
int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
void dfs(int x)
{
    for(int i=0;i<id[x].size();i++)
    {
        ans[id[x][i]]-=colsum[c1[x][i]]*imp[x][i];
        ans[id[x][i]]+=colnum[c1[x][i]]*c2[x][i]*imp[x][i];
    }
    for(int i=st[x];i;i=nex[i])
    {
        if(to[i]==fa[x])continue;
        colsum[col[i]]+=val[i];
        colnum[col[i]]++;
        dfs(to[i]);
        colsum[col[i]]-=val[i];
        colnum[col[i]]--;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int x,y,v,color;
        //cin>>x>>y>>color>>v;
        scanf("%d%d%d%d",&x,&y,&color,&v);
        addedge(x,y,v,color);
        addedge(y,x,v,color);
    }
    dfs1(1);
    dfs2(1,1);
    //cout<<sum[4]-sum[1];
    //cout<<LCA(4,3)<<endl;
    for(int i=1;i<=m;i++)
    {
        int x,y,u,v,z;
        //cin>>u>>v>>x>>y;
        scanf("%d%d%d%d",&u,&v,&x,&y);
        z=LCA(x,y);
        ans[i]=sum[x]+sum[y]-2*sum[z];
        c1[x].push_back(u);
        c2[x].push_back(v);
        id[x].push_back(i);
        imp[x].push_back(1);
        c1[y].push_back(u);
        c2[y].push_back(v);
        id[y].push_back(i);
        imp[y].push_back(1);
        c1[z].push_back(u);
        c2[z].push_back(v);
        id[z].push_back(i);
        imp[z].push_back(-2);
    }
    dfs(1);
    for(int i=1;i<=m;i++)
    {
        //cout<<ans[i]<<endl;
        printf("%d\n",ans[i]);
    }
    return 0;
}