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 N=1e5+5;
int tot,id,n,q,dis[N],dep[N],root[N],head[N],nex[N<<1],to[N<<1],c[N<<1],wi[N<<1];
int fa[N][20],lg[N];
struct node
{
    int tot,sum,l,r;
}t[N*40];
void add(int u,int v,int x,int y)
{
    to[++tot]=v;nex[tot]=head[u];head[u]=tot;c[tot]=x;wi[tot]=y;
}
int build(int l,int r,int k)
{
    int p=++id;
    if(l==r) return p;
    int m=l+r>>1;
    t[p].l=build(l,m,k<<1);
    t[p].r=build(m+1,r,k<<1|1);
    return p;
}
int update(int l,int r,int k,int x,int v,int pre)
{
    int p=++id;
    if(l==r) {t[p].sum=t[pre].sum+v;t[p].tot=t[pre].tot+1;return p;}
    int m=l+r>>1;
    if(x<=m)
    {
        t[p].r=t[pre].r;
        t[p].l=update(l,m,k<<1,x,v,t[pre].l);
    }
    else
    {
        t[p].l=t[pre].l;
        t[p].r=update(m+1,r,k<<1|1,x,v,t[pre].r);
    }
    return p;
}
pair<int,int> query(int l,int r,int k,int x,int now,int pre)
{
    if(l==r) return {t[now].tot-t[pre].tot,t[now].sum-t[pre].sum};
    int m=l+r>>1;
    if(x<=m) return query(l,m,k<<1,x,t[now].l,t[pre].l);
    return query(m+1,r,k<<1|1,x,t[now].r,t[pre].r);
}
void dfs(int u,int p)
{
    dep[u]=dep[p]+1;
    fa[u][0]=p;
    for(int i=1;1<<i<=dep[u];i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=nex[i])
    {
        int v=to[i];
        if(v==p) continue;
        root[v]=update(1,n-1,1,c[i],wi[i],root[u]);
        dis[v]=dis[u]+wi[i];
        dfs(v,u);
    }
}
int LCA(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    while(dep[u]>dep[v])
        u=fa[u][lg[dep[u]-dep[v]]-1];
    if(u==v) return u;
    for(int k=lg[dep[u]]-1;k>=0;k--)
        if(fa[u][k]!=fa[v][k])
            u=fa[u][k],v=fa[v][k];
    return fa[u][0];
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        int u,v,x,y;
        scanf("%d%d%d%d",&u,&v,&x,&y);
        add(u,v,x,y);
        add(v,u,x,y);
    }
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    root[1]=build(1,n-1,1);
    dfs(1,0);
    while(q--)
    {
        int x,y,u,v;
        scanf("%d%d%d%d",&x,&y,&u,&v);
        int lca=LCA(u,v);
        if(dep[u]>dep[v]) swap(u,v);
        int ans=dis[v]-dis[lca]+dis[u]-dis[lca];
        pair<int,int>t1=query(1,n-1,1,x,root[v],root[lca]),t2=query(1,n-1,1,x,root[u],root[lca]);
        ans=ans-t1.second+t1.first*y-t2.second+t2.first*y;
        printf("%d\n",ans);
    }
}