#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20],len; len=0;
	if(x<0)x=-x,putchar('-');
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
struct edge{
	int to,nxt,d,col;
}e[2*maxn];
struct query{
	int x,col,d,id,w;
}q[4*maxn];
int fir[maxn],fa[maxn],dep[maxn],size[maxn],hson[maxn],top[maxn],id[maxn];
ll dist[maxn];
ll sum[maxn],cnt[maxn],ans[maxn];
int n,m,tot,last;
inline void add_edge(int x,int y,int z,int w){e[tot].to=y; e[tot].col=z; e[tot].d=w; e[tot].nxt=fir[x]; fir[x]=tot++;}
void dfs1(int now)
{
	size[now]=1; hson[now]=0; id[now]=++tot;
	for(int i=fir[now];~i;i=e[i].nxt)
		if(e[i].to!=fa[now]){
			fa[e[i].to]=now; dep[e[i].to]=dep[now]+1;
			dist[e[i].to]=dist[now]+e[i].d;
			dfs1(e[i].to);
			size[now]+=size[e[i].to];
			if(size[e[i].to]>size[hson[now]])hson[now]=e[i].to;
		}
}
void dfs2(int now,int tp)
{
	top[now]=tp;
	if(hson[now])dfs2(hson[now],tp);
	for(int i=fir[now];~i;i=e[i].nxt)
		if(e[i].to!=fa[now]&&e[i].to!=hson[now])dfs2(e[i].to,e[i].to);
}
inline int getlca(int x,int y)
{
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){int tmp=x; x=y; y=tmp;}
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
bool cmp(query x,query y){return id[x.x]<id[y.x];}
void solve(int now)
{
	while(last<=tot&&id[q[last].x]==id[now]){
		ans[q[last].id]+=q[last].w*(dist[now]-sum[q[last].col]+(ll)cnt[q[last].col]*q[last].d);
		++last;
	}
	for(int i=fir[now];~i;i=e[i].nxt)
		if(e[i].to!=fa[now]){
			sum[e[i].col]+=e[i].d; ++cnt[e[i].col];
			solve(e[i].to);
			sum[e[i].col]-=e[i].d; --cnt[e[i].col];
		}
}
int main()
{
	n=read(); m=read();
	memset(fir,255,sizeof(fir));
	for(int i=1;i<n;i++){
		int x=read(),y=read(),z=read(),w=read();
		add_edge(x,y,z,w); add_edge(y,x,z,w);
	}
	fa[1]=dep[1]=0; tot=0;
	dfs1(1);
	dfs2(1,1);
	tot=0;
	for(int i=1;i<=m;i++){
		int col=read(),d=read(),x=read(),y=read();
		int lca=getlca(x,y);
		q[++tot]={x,col,d,i,1};
		q[++tot]={y,col,d,i,1};
		q[++tot]={lca,col,d,i,-1};
		q[++tot]={lca,col,d,i,-1};
	}
	std::sort(q+1,q+tot+1,cmp);
	last=1;
	solve(1);
	for(int i=1;i<=m;i++)
		writeln(ans[i]);
	return 0;
}
### Prompt

Please formulate 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<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20],len; len=0;
	if(x<0)x=-x,putchar('-');
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
struct edge{
	int to,nxt,d,col;
}e[2*maxn];
struct query{
	int x,col,d,id,w;
}q[4*maxn];
int fir[maxn],fa[maxn],dep[maxn],size[maxn],hson[maxn],top[maxn],id[maxn];
ll dist[maxn];
ll sum[maxn],cnt[maxn],ans[maxn];
int n,m,tot,last;
inline void add_edge(int x,int y,int z,int w){e[tot].to=y; e[tot].col=z; e[tot].d=w; e[tot].nxt=fir[x]; fir[x]=tot++;}
void dfs1(int now)
{
	size[now]=1; hson[now]=0; id[now]=++tot;
	for(int i=fir[now];~i;i=e[i].nxt)
		if(e[i].to!=fa[now]){
			fa[e[i].to]=now; dep[e[i].to]=dep[now]+1;
			dist[e[i].to]=dist[now]+e[i].d;
			dfs1(e[i].to);
			size[now]+=size[e[i].to];
			if(size[e[i].to]>size[hson[now]])hson[now]=e[i].to;
		}
}
void dfs2(int now,int tp)
{
	top[now]=tp;
	if(hson[now])dfs2(hson[now],tp);
	for(int i=fir[now];~i;i=e[i].nxt)
		if(e[i].to!=fa[now]&&e[i].to!=hson[now])dfs2(e[i].to,e[i].to);
}
inline int getlca(int x,int y)
{
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){int tmp=x; x=y; y=tmp;}
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
bool cmp(query x,query y){return id[x.x]<id[y.x];}
void solve(int now)
{
	while(last<=tot&&id[q[last].x]==id[now]){
		ans[q[last].id]+=q[last].w*(dist[now]-sum[q[last].col]+(ll)cnt[q[last].col]*q[last].d);
		++last;
	}
	for(int i=fir[now];~i;i=e[i].nxt)
		if(e[i].to!=fa[now]){
			sum[e[i].col]+=e[i].d; ++cnt[e[i].col];
			solve(e[i].to);
			sum[e[i].col]-=e[i].d; --cnt[e[i].col];
		}
}
int main()
{
	n=read(); m=read();
	memset(fir,255,sizeof(fir));
	for(int i=1;i<n;i++){
		int x=read(),y=read(),z=read(),w=read();
		add_edge(x,y,z,w); add_edge(y,x,z,w);
	}
	fa[1]=dep[1]=0; tot=0;
	dfs1(1);
	dfs2(1,1);
	tot=0;
	for(int i=1;i<=m;i++){
		int col=read(),d=read(),x=read(),y=read();
		int lca=getlca(x,y);
		q[++tot]={x,col,d,i,1};
		q[++tot]={y,col,d,i,1};
		q[++tot]={lca,col,d,i,-1};
		q[++tot]={lca,col,d,i,-1};
	}
	std::sort(q+1,q+tot+1,cmp);
	last=1;
	solve(1);
	for(int i=1;i<=m;i++)
		writeln(ans[i]);
	return 0;
}
```