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;
int n,m;
const int N=1e5+100;
int dis[N],d[N],f[N][20],root[N*40],lg[N];
struct edgd
{
	int v,c,w,nxt;
}e[N<<2];
int h[N],idx=0;
void add(int u,int v,int c,int w)
{
	e[++idx]={v,c,w,h[u]};
	h[u]=idx;
}
struct node
{
	int l,r,tot,sum;
} t[N*40];
int cnt=0;
void build(int l,int r,int &x)
{
	x=++cnt;
	t[x].sum=t[x].tot=0;
	if(l==r) return ;
	int mid=l+r>>1;
	build(l,mid,t[x].l);
	build(mid+1,r,t[x].r);
}
void update(int l,int r,int c,int w,int &x,int pre)
{
	x=++cnt;
	t[x]=t[pre];
	if(l==r)
	{
		t[x].sum+=w;
		t[x].tot++;
		return ;
	}
	int mid=l+r>>1;
	if(c<=mid)update(l,mid,c,w,t[x].l,t[pre].l);
    else  update(mid+1,r,c,w,t[x].r,t[pre].r);
}
pair<int,int> query(int l,int r,int x,int y,int pos)
{
	if(l==r)return {t[y].sum-t[x].sum,t[y].tot-t[x].tot};
	int mid=l+r>>1;
	if(pos<=mid) return query(l,mid,t[x].l,t[y].l,pos);
	else return query(mid+1,r,t[x].r,t[y].r,pos);
} 
void dfs(int x,int fa)
{
	f[x][0]=fa;
	for(int i=1;1<<i<=d[x];i++) f[x][i]=f[f[x][i-1]][i-1];
	for(int i=h[x];i;i=e[i].nxt)
	{
		int v=e[i].v,c=e[i].c,w=e[i].w;
		if(v==fa) continue;
		update(1,n-1,c,w,root[v],root[x]);
		dis[v]=dis[x]+w;
		d[v]=d[x]+1; 
		dfs(v,x);
	}
}
int LCA(int x,int y)
{
	if(d[x]<d[y]) swap(x,y);
	int del=d[x]-d[y];
	for(int i=0;i<=lg[d[x]];i++) 
	 if(1<<i&del) x=f[x][i];
	if(x==y) return x;
	for(int i=lg[d[x]]-1;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		x=f[x][i],y=f[y][i];
	}
	return f[x][0];
}
int main()
{
	cin>>n>>m;
	for(int i=1,x,y,z,w;i<n;i++) 
	{
		cin>>x>>y>>z>>w;
		add(x,y,z,w);add(y,x,z,w);
	}
	for(int i=1;i<=n;i++)  lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	build(1,n,root[1]);
    dfs(1,0);
    //for(int i=1;i<=n;i++) cout<<dis[i]<<endl; 
    while(m--)
    {
    	int x,y,u,v;
    	cin>>x>>y>>u>>v;
    	int lca=LCA(u,v);
    	if(d[u]>d[v])swap(u,v);
    	if(lca==u)
    	{
    		int ans=dis[v]-dis[lca];
    		pair<int,int>t=query(1,n-1,root[u],root[v],x);
    		ans=ans-t.first+t.second*y;
    		cout<<ans<<endl;
    	}
    	else
    	{
    		int ans=dis[v]-dis[lca]+dis[u]-dis[lca];
            pair<int,int>t1=query(1,n-1,root[lca],root[v],x),t2=query(1,n-1,root[lca],root[u],x);
            ans=ans-t1.first+t1.second*y-t2.first+t2.second*y;
            cout<<ans<<endl;
    	}
    }
	return 0; 
}