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;
const int maxn=1e5+10;
struct edge
{
    int to,col,val;
    edge(int _to=0,int _col=0,int _val=0)
    {
        to=_to;
        col=_col;
        val=_val;
    }
};
vector<edge>G[maxn];

struct Query
{
    int op,col,val,id;
    Query(int _op=0,int _col=0,int _val=0,int _id=0)
    {
        op=_op;
        col=_col;
        val=_val;
        id=_id;
    }
};
vector<Query>query[maxn];

int n,Q,ans[maxn],c[maxn],d[maxn];

void dfs(int v,int fa,int sum)
{

    for(int i=query[v].size()-1;i>=0;i--)
    {
        Query e=query[v][i];
        int tmp=sum-c[e.col]+d[e.col]*e.val;
        if(e.op==1)
            ans[e.id]+=tmp;
        else
            ans[e.id]-=2*tmp;
    }

    for(int i=G[v].size()-1;i>=0;i--)
    {

        edge e=G[v][i];
        if(e.to==fa)
            continue;
        c[e.col]+=e.val;
        d[e.col]++;
        dfs(e.to,v,sum+e.val);
        c[e.col]-=e.val;
        d[e.col]--;
    }
}


int lg[maxn],f[maxn][22],dep[maxn];

void pre_dfs(int v,int fa)
{
    dep[v]=dep[fa]+1;
    f[v][0]=fa;
    for(int i=1;(1<<i)<=dep[v];i++)
        f[v][i]=f[f[v][i-1]][i-1];
    for(int i=G[v].size()-1;i>=0;i--)
    {
        int u=G[v][i].to;
        if(u==fa)
            continue;
        pre_dfs(u,v);
    }
}

int LCA(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    while(dep[x]!=dep[y])
    {
        int h=lg[dep[x]-dep[y]];
        x=f[x][h];
    }
    if(x==y)
        return x;
    for(int i=lg[dep[x]];i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    for(int i=2;i<maxn;i++)
        lg[i]=lg[i/2]+1;

    scanf("%d%d",&n,&Q);
    for(int i=1;i<n;i++)
    {
        int A,B,C,D;scanf("%d%d%d%d",&A,&B,&C,&D);
        G[A].push_back(edge(B,C,D));
        G[B].push_back(edge(A,C,D));
    }

    pre_dfs(1,0);

    for(int i=1;i<=Q;i++)
    {
        int x,y,u,v;
        scanf("%d%d%d%d",&x,&y,&u,&v);
        int w=LCA(u,v);
        query[u].push_back(Query(1,x,y,i));
        query[v].push_back(Query(1,x,y,i));
        query[w].push_back(Query(-1,x,y,i));
    }
    dfs(1,0,0);
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]);
    return 0;
}