#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,d,w,a,b,c,dp[N],sn[N],rt[N],sz[N],tp[N],fa[N],L,ans,h[N];
struct E{
	int l,to,w,c;
}e[N<<1];
struct P{
	int ls,rs,w,s;
}tr[3000005];
void Ad(int nt,int ot,int z,int y){
	tr[nt]=tr[ot];
	tr[nt].w+=w;
	if(z==y){
		tr[nt].s++;
		return;
	}
	int mid=z+y>>1;
	if(d<=mid)Ad(tr[nt].ls=++L,tr[ot].ls,z,mid);
	else Ad(tr[nt].rs=++L,tr[ot].rs,mid+1,y);
}
void Qr(int zt,int yt,int lt,int z,int y){
	if(z==y){
//		printf("%d_%d_\n",z,tr[yt].s);
		ans-=tr[zt].w+tr[yt].w-(tr[lt].w<<1);
		ans+=b*(tr[zt].s+tr[yt].s-(tr[lt].s<<1));
		return;
	}
	int mid=z+y>>1;
	if(a<=mid)Qr(tr[zt].ls,tr[yt].ls,tr[lt].ls,z,mid);
	else Qr(tr[zt].rs,tr[yt].rs,tr[lt].rs,mid+1,y);
}
void se(int x,int f){
	sz[x]=1;
	for(int i=h[x];i;i=e[i].l){
		if(e[i].to!=f){
			d=e[i].c;w=e[i].w;
			Ad(rt[e[i].to]=++L,rt[x],1,n);
//			printf("%d %d",i,e[i].to);
			se(e[i].to,x);
			sz[x]+=sz[e[i].to];
			if(sz[e[i].to]>sz[sn[x]])sn[x]=e[i].to;
		}
	}
}
void dfs(int x,int f,int T){
	tp[x]=T;dp[x]=dp[f]+1;
	fa[x]=f;
	if(sn[x])dfs(sn[x],x,T);
	for(int i=h[x];i;i=e[i].l){
		if(e[i].to!=f&&e[i].to!=sn[x])dfs(e[i].to,x,e[i].to);
	}
}
int lca(int x,int y){
	while(tp[x]!=tp[y]){
		if(dp[tp[x]]<dp[tp[y]])swap(x,y);
		x=fa[tp[x]];
	}
	return dp[x]<dp[y]? x:y;
}
int main(){
	int x,y;
	scanf("%d %d",&n,&m);
	for(int i=1;i<n;++i){
		scanf("%d %d %d %d",&x,&y,&c,&w);
		e[i<<1].w=e[i<<1|1].w=w;
		e[i<<1].c=e[i<<1|1].c=c;
		e[i<<1].to=y;e[i<<1].l=h[x];h[x]=i<<1;
		e[i<<1|1].to=x;e[i<<1|1].l=h[y];h[y]=i<<1|1;
	}
	se(1,0);dfs(1,0,1);
	for(int i=1;i<=m;++i){
		scanf("%d %d %d %d",&a,&b,&c,&d);
		int z=lca(c,d);ans=0;
		Qr(rt[c],rt[d],rt[z],1,n);
		ans+=tr[rt[c]].w+tr[rt[d]].w-(tr[rt[z]].w<<1);
		printf("%d\n",ans);
	}
}
### Prompt

Generate a cpp solution to the following 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

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,d,w,a,b,c,dp[N],sn[N],rt[N],sz[N],tp[N],fa[N],L,ans,h[N];
struct E{
	int l,to,w,c;
}e[N<<1];
struct P{
	int ls,rs,w,s;
}tr[3000005];
void Ad(int nt,int ot,int z,int y){
	tr[nt]=tr[ot];
	tr[nt].w+=w;
	if(z==y){
		tr[nt].s++;
		return;
	}
	int mid=z+y>>1;
	if(d<=mid)Ad(tr[nt].ls=++L,tr[ot].ls,z,mid);
	else Ad(tr[nt].rs=++L,tr[ot].rs,mid+1,y);
}
void Qr(int zt,int yt,int lt,int z,int y){
	if(z==y){
//		printf("%d_%d_\n",z,tr[yt].s);
		ans-=tr[zt].w+tr[yt].w-(tr[lt].w<<1);
		ans+=b*(tr[zt].s+tr[yt].s-(tr[lt].s<<1));
		return;
	}
	int mid=z+y>>1;
	if(a<=mid)Qr(tr[zt].ls,tr[yt].ls,tr[lt].ls,z,mid);
	else Qr(tr[zt].rs,tr[yt].rs,tr[lt].rs,mid+1,y);
}
void se(int x,int f){
	sz[x]=1;
	for(int i=h[x];i;i=e[i].l){
		if(e[i].to!=f){
			d=e[i].c;w=e[i].w;
			Ad(rt[e[i].to]=++L,rt[x],1,n);
//			printf("%d %d",i,e[i].to);
			se(e[i].to,x);
			sz[x]+=sz[e[i].to];
			if(sz[e[i].to]>sz[sn[x]])sn[x]=e[i].to;
		}
	}
}
void dfs(int x,int f,int T){
	tp[x]=T;dp[x]=dp[f]+1;
	fa[x]=f;
	if(sn[x])dfs(sn[x],x,T);
	for(int i=h[x];i;i=e[i].l){
		if(e[i].to!=f&&e[i].to!=sn[x])dfs(e[i].to,x,e[i].to);
	}
}
int lca(int x,int y){
	while(tp[x]!=tp[y]){
		if(dp[tp[x]]<dp[tp[y]])swap(x,y);
		x=fa[tp[x]];
	}
	return dp[x]<dp[y]? x:y;
}
int main(){
	int x,y;
	scanf("%d %d",&n,&m);
	for(int i=1;i<n;++i){
		scanf("%d %d %d %d",&x,&y,&c,&w);
		e[i<<1].w=e[i<<1|1].w=w;
		e[i<<1].c=e[i<<1|1].c=c;
		e[i<<1].to=y;e[i<<1].l=h[x];h[x]=i<<1;
		e[i<<1|1].to=x;e[i<<1|1].l=h[y];h[y]=i<<1|1;
	}
	se(1,0);dfs(1,0,1);
	for(int i=1;i<=m;++i){
		scanf("%d %d %d %d",&a,&b,&c,&d);
		int z=lca(c,d);ans=0;
		Qr(rt[c],rt[d],rt[z],1,n);
		ans+=tr[rt[c]].w+tr[rt[d]].w-(tr[rt[z]].w<<1);
		printf("%d\n",ans);
	}
}
```