#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,m,s,e,k,c,HEAD[N],b,Ne[N*2],E[N*2],C[N*2],K[N*2];
int F[N],D[N],Le[N],SZ[N],SON[N],TOP[N],DF[N];
int df,L[N],R[N],CNe[N<<1],CH[N],ANS[N];
struct V {
	int s,e,k,c,sum,csum,cle,num;
	bool operator <(const V a)const {
		return k<a.k;
	}
} Q[N];
struct X {
	int sum,le;
} O[N];
void ADD(int s,int e) {
	Ne[++b]=HEAD[s],HEAD[s]=b;
	E[b]=e,C[b]=c,K[b]=k;
}
void SUM(int k,int l,int i,int _) {
	while(l)Q[i].csum+=O[l+L[k]-1].sum*_,Q[i].cle+=O[l+L[k]-1].le*_,l-=l&-l;
}
void INSERT(int k,int o,int sum,int le) {
//	printf("%d %d %d %d\n",k,o,sum,le);
	while(o<=R[k]-L[k]+1) {
		O[o+L[k]-1].sum+=sum;
		O[o+L[k]-1].le+=le;
		o+=o&-o;
	}
}
void DFS(int i,int f) {
	D[i]=D[f]+1;
	F[i]=f;
	for(int z=HEAD[i]; z; z=Ne[z]) {
		if(E[z]!=f) {
			CNe[z]=CH[K[z]],CH[K[z]]=z;
			Le[E[z]]=Le[i]+C[z];
			DFS(E[z],i);
			SZ[i]+=SZ[E[z]];
			if(SZ[E[z]]>SZ[SON[i]])SON[i]=E[z];
		}
	}
	SZ[i]++;
}
void DO(int i,int top) {
	DF[i]=++df;
	if(i==top)L[i]=df;
	TOP[i]=top;
	if(SON[i])DO(SON[i],top);
	else R[top]=df;
	for(int z=HEAD[i]; z; z=Ne[z])
		if(E[z]!=F[i]&&E[z]!=SON[i]) DO(E[z],E[z]);
}
void So(int i) {
	s=Q[i].s,e=Q[i].e;
	while(TOP[s]^TOP[e]) {
		if(D[TOP[s]]<D[TOP[e]])swap(s,e);
		Q[i].sum+=Le[s]-Le[F[TOP[s]]];
		SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,-1),s=F[TOP[s]];
	}
	if(D[s]<D[e])swap(s,e);
	Q[i].sum+=Le[s]-Le[e];
	SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,-1);
	SUM(TOP[e],DF[e]-L[TOP[s]]+1,i,1);
}
void AN(int i) {
	s=Q[i].s,e=Q[i].e;
	while(TOP[s]^TOP[e]) {
		if(D[TOP[s]]<D[TOP[e]])swap(s,e);
		SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,1),s=F[TOP[s]];
	}
	if(D[s]<D[e])swap(s,e);
	SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,1);
	SUM(TOP[e],DF[e]-L[TOP[s]]+1,i,-1);
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1; i<n; i++) {
		scanf("%d %d %d %d",&s,&e,&k,&c);
		ADD(s,e),ADD(e,s);
	}
	DFS(1,0),DO(1,1);
//	for(int i=1; i<=n; i++)
	for(int i=1; i<=m; i++)
		Q[i].num=i,scanf("%d %d %d %d",&Q[i].k,&Q[i].c,&Q[i].s,&Q[i].e);
	sort(Q+1,Q+m+1);
	for(int i=1,j; i<=m;) {
		j=i;
		while(Q[j].k==Q[i].k) {
			So(j);
			j++;
		}
		for(int z=CH[Q[i].k]; z; z=CNe[z]) {

			INSERT(TOP[E[z]],DF[E[z]]-L[TOP[E[z]]]+1,1,C[z]);
//			printf("	%d %d %d\n",Q[i].k,E[z],C[z]);
		}
		while(i<j) {
			AN(i);
			ANS[Q[i].num]=Q[i].sum-Q[i].cle+Q[i].csum*Q[i].c;
			i++;
		}
	}
	for(int i=1; i<=m; i++)printf("%d\n",ANS[i]);
	return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

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;
#define N 100005
int n,m,s,e,k,c,HEAD[N],b,Ne[N*2],E[N*2],C[N*2],K[N*2];
int F[N],D[N],Le[N],SZ[N],SON[N],TOP[N],DF[N];
int df,L[N],R[N],CNe[N<<1],CH[N],ANS[N];
struct V {
	int s,e,k,c,sum,csum,cle,num;
	bool operator <(const V a)const {
		return k<a.k;
	}
} Q[N];
struct X {
	int sum,le;
} O[N];
void ADD(int s,int e) {
	Ne[++b]=HEAD[s],HEAD[s]=b;
	E[b]=e,C[b]=c,K[b]=k;
}
void SUM(int k,int l,int i,int _) {
	while(l)Q[i].csum+=O[l+L[k]-1].sum*_,Q[i].cle+=O[l+L[k]-1].le*_,l-=l&-l;
}
void INSERT(int k,int o,int sum,int le) {
//	printf("%d %d %d %d\n",k,o,sum,le);
	while(o<=R[k]-L[k]+1) {
		O[o+L[k]-1].sum+=sum;
		O[o+L[k]-1].le+=le;
		o+=o&-o;
	}
}
void DFS(int i,int f) {
	D[i]=D[f]+1;
	F[i]=f;
	for(int z=HEAD[i]; z; z=Ne[z]) {
		if(E[z]!=f) {
			CNe[z]=CH[K[z]],CH[K[z]]=z;
			Le[E[z]]=Le[i]+C[z];
			DFS(E[z],i);
			SZ[i]+=SZ[E[z]];
			if(SZ[E[z]]>SZ[SON[i]])SON[i]=E[z];
		}
	}
	SZ[i]++;
}
void DO(int i,int top) {
	DF[i]=++df;
	if(i==top)L[i]=df;
	TOP[i]=top;
	if(SON[i])DO(SON[i],top);
	else R[top]=df;
	for(int z=HEAD[i]; z; z=Ne[z])
		if(E[z]!=F[i]&&E[z]!=SON[i]) DO(E[z],E[z]);
}
void So(int i) {
	s=Q[i].s,e=Q[i].e;
	while(TOP[s]^TOP[e]) {
		if(D[TOP[s]]<D[TOP[e]])swap(s,e);
		Q[i].sum+=Le[s]-Le[F[TOP[s]]];
		SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,-1),s=F[TOP[s]];
	}
	if(D[s]<D[e])swap(s,e);
	Q[i].sum+=Le[s]-Le[e];
	SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,-1);
	SUM(TOP[e],DF[e]-L[TOP[s]]+1,i,1);
}
void AN(int i) {
	s=Q[i].s,e=Q[i].e;
	while(TOP[s]^TOP[e]) {
		if(D[TOP[s]]<D[TOP[e]])swap(s,e);
		SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,1),s=F[TOP[s]];
	}
	if(D[s]<D[e])swap(s,e);
	SUM(TOP[s],DF[s]-L[TOP[s]]+1,i,1);
	SUM(TOP[e],DF[e]-L[TOP[s]]+1,i,-1);
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1; i<n; i++) {
		scanf("%d %d %d %d",&s,&e,&k,&c);
		ADD(s,e),ADD(e,s);
	}
	DFS(1,0),DO(1,1);
//	for(int i=1; i<=n; i++)
	for(int i=1; i<=m; i++)
		Q[i].num=i,scanf("%d %d %d %d",&Q[i].k,&Q[i].c,&Q[i].s,&Q[i].e);
	sort(Q+1,Q+m+1);
	for(int i=1,j; i<=m;) {
		j=i;
		while(Q[j].k==Q[i].k) {
			So(j);
			j++;
		}
		for(int z=CH[Q[i].k]; z; z=CNe[z]) {

			INSERT(TOP[E[z]],DF[E[z]]-L[TOP[E[z]]]+1,1,C[z]);
//			printf("	%d %d %d\n",Q[i].k,E[z],C[z]);
		}
		while(i<j) {
			AN(i);
			ANS[Q[i].num]=Q[i].sum-Q[i].cle+Q[i].csum*Q[i].c;
			i++;
		}
	}
	for(int i=1; i<=m; i++)printf("%d\n",ANS[i]);
	return 0;
}
```