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>
#define pb push_back
using namespace std;
const int N=1e5+10; 
const int lg=18;
int n,q;
int a,b,c,d,y,U,V,fa,ID;
int tmp,num,len1,len2;
int pos[N],ans[N],sum[N];//欧拉序中对应编号 答案 链上的和 
int bit1[N*2],bit2[N*2];//树按颜色建一棵 按查询建一棵 
int dep[N],dis[N];//点的深度 实际边边权
int head[N],v[N*2],nex[N*2],id[N*2],cnt;
int in[N],out[N];
int dfn[N*2],tot;
int dp[N*2][lg];
//欧拉序 dfn点戳 in out边戳 第i条边[in,out)
struct query{int id,y,u,v;};
vector<int>col[N];//把树边放入对应颜色 
vector<query>color[N];//把询问放入对应颜色 
int mn(int u,int v){if(dep[u]<dep[v])return u;else return v;};
void link(int x,int y,int i){v[++cnt]=y;nex[cnt]=head[x];id[cnt]=i;head[x]=cnt;}
void add(int *tr,int x,int v){for(int i=x;i<=tot;i+=i&-i)tr[i]+=v;}
int ask(int *tr,int x){int ans=0;for(int i=x;i>0;i-=i&-i)ans+=tr[i];return ans;}
void dfs(int u,int fa,int d)
{
	dfn[++tot]=u;
	pos[u]=tot;
	dep[u]=d;
	for(int i=head[u];i;i=nex[i])
	{
		int to=v[i],num=id[i],w=dis[num];//边的真实编号 
		if(to==fa)continue;
		in[num]=tot+1;//归远端节点 即下一个搜的节点 
		sum[to]=sum[u]+w;
		dfs(to,u,d+1);
		dfn[++tot]=u;
		out[num]=tot;
	}
}
void init(int up)
{
	for(int i=1;i<=up;++i)
	dp[i][0]=dfn[i];
	for(int len=1;(1<<len)<=up;++len)
	for(int i=1;i+(1<<len)-1<=up;++i)
	dp[i][len]=mn(dp[i][len-1],dp[i+(1<<(len-1))][len-1]);
} 
int lca(int u,int v)
{
	int l=pos[u],r=pos[v];
	if(l==r)return dp[l][0]; 
	if(l>r)swap(l,r);
	int k=log(r-l+1)/log(2);
	return mn(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;++i)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		link(a,b,i);link(b,a,i);
		col[c].pb(i);dis[i]=d;
	}
	dfs(1,-1,0); 
	init(tot);
	for(int i=1;i<=q;++i)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		color[a].pb(query{i,b,c,d});
	}
	for(int i=1;i<n;++i)
	{
		if(!color[i].size())continue;//没有询问 
		len1=col[i].size();
		for(int j=0;j<len1;++j)
		{
			num=col[i][j];
			add(bit1,in[num],1);
			add(bit1,out[num],-1);
			add(bit2,in[num],dis[num]);
			add(bit2,out[num],-dis[num]);
		}
		len2=color[i].size();
		for(int j=0;j<len2;++j)
		{
			ID=color[i][j].id;y=color[i][j].y;
			U=color[i][j].u;V=color[i][j].v;
			fa=lca(U,V);
			tmp=sum[U]+sum[V]-2*sum[fa];
			tmp-=(ask(bit2,pos[U])+ask(bit2,pos[V])-2*ask(bit2,pos[fa]));
			tmp+=y*(ask(bit1,pos[U])+ask(bit1,pos[V])-2*ask(bit1,pos[fa]));
			ans[ID]=tmp;
		}
		for(int j=0;j<len1;++j)
		{
			num=col[i][j];
			add(bit1,in[num],-1);
			add(bit1,out[num],1);
			add(bit2,in[num],-dis[num]);
			add(bit2,out[num],dis[num]);
		}
	}
	for(int i=1;i<=q;++i)
	printf("%d\n",ans[i]);
	return 0;
}