#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int n,fir[100010],dis[200010],nxt[200010],w[200010],id;
il vd link(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
int pa[100010],pb[100010],pc[100010],pd[100010];
int qx[100010],qy[100010],qu[100010],qv[100010];
std::vector<int>Ge[100010],Gq[100010];
ll t1[100010],t2[100010];
il vd update(ll*t,int p,int x){while(p<=n)t[p]+=x,p+=p&-p;}
il ll query(ll*t,int p){ll ret=0;while(p)ret+=t[p],p-=p&-p;return ret;}
int fa[100010],dfn[100010];
ll dist[100010];
int son[100010],siz[100010],top[100010],dep[100010];
il vd dfs(int x){
	dfn[x]=++dfn[0];siz[x]=1;
	for(int i=fir[x];i;i=nxt[i]){
		if(fa[x]==dis[i])continue;
		fa[dis[i]]=x;
		dist[dis[i]]=dist[x]+w[i];
		dep[dis[i]]=dep[x]+1;
		dfs(dis[i]);
		siz[x]+=siz[dis[i]];
		if(siz[son[x]]<siz[dis[i]])son[x]=dis[i];
	}
}
il vd dfs(int x,int tp){
	top[x]=tp;if(son[x])dfs(son[x],tp);
	for(int i=fir[x];i;i=nxt[i])if(fa[x]!=dis[i]&&son[x]!=dis[i])dfs(dis[i],dis[i]);
}
il int LCA(int a,int b){
	while(top[a]^top[b])
		if(dep[top[a]]>dep[top[b]])a=fa[top[a]];
		else b=fa[top[b]];
	return dep[a]>dep[b]?b:a;
}
ll ans[100010];
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	n=gi();int Q=gi();
	for(int i=1;i<n;++i)pa[i]=gi(),pb[i]=gi(),pc[i]=gi(),pd[i]=gi(),link(pa[i],pb[i],pd[i]),link(pb[i],pa[i],pd[i]),Ge[pc[i]].push_back(i);
	for(int i=1;i<=Q;++i)qx[i]=gi(),qy[i]=gi(),qu[i]=gi(),qv[i]=gi(),Gq[qx[i]].push_back(i);
	dfs(1);dfs(1,1);
	for(int i=1;i<n;++i)if(pb[i]==fa[pa[i]])std::swap(pa[i],pb[i]);
	for(int i=1;i<=Q;++i)ans[i]=dist[qu[i]]+dist[qv[i]]-2*dist[LCA(qu[i],qv[i])];
	for(int i=1;i<n;++i){
		for(int j:Ge[i])update(t1,dfn[pb[j]],1),update(t1,dfn[pb[j]]+siz[pb[j]],-1);
		for(int j:Ge[i])update(t2,dfn[pb[j]],pd[j]),update(t2,dfn[pb[j]]+siz[pb[j]],-pd[j]);
		for(int j:Gq[i]){
			int a=qu[j],b=qv[j],c=LCA(a,b);
			ans[j]-=query(t2,dfn[a])+query(t2,dfn[b])-2*query(t2,dfn[c]);
			ans[j]+=qy[j]*(query(t1,dfn[a])+query(t1,dfn[b])-2*query(t1,dfn[c]));
		}
		for(int j:Ge[i])update(t1,dfn[pb[j]],-1),update(t1,dfn[pb[j]]+siz[pb[j]],1);
		for(int j:Ge[i])update(t2,dfn[pb[j]],-pd[j]),update(t2,dfn[pb[j]]+siz[pb[j]],pd[j]);
	}
	for(int i=1;i<=Q;++i)printf("%lld\n",ans[i]);
	return 0;
}

### Prompt

Please provide a CPP coded solution 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>
#define il inline
#define vd void
typedef long long ll;
il ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int n,fir[100010],dis[200010],nxt[200010],w[200010],id;
il vd link(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;}
int pa[100010],pb[100010],pc[100010],pd[100010];
int qx[100010],qy[100010],qu[100010],qv[100010];
std::vector<int>Ge[100010],Gq[100010];
ll t1[100010],t2[100010];
il vd update(ll*t,int p,int x){while(p<=n)t[p]+=x,p+=p&-p;}
il ll query(ll*t,int p){ll ret=0;while(p)ret+=t[p],p-=p&-p;return ret;}
int fa[100010],dfn[100010];
ll dist[100010];
int son[100010],siz[100010],top[100010],dep[100010];
il vd dfs(int x){
	dfn[x]=++dfn[0];siz[x]=1;
	for(int i=fir[x];i;i=nxt[i]){
		if(fa[x]==dis[i])continue;
		fa[dis[i]]=x;
		dist[dis[i]]=dist[x]+w[i];
		dep[dis[i]]=dep[x]+1;
		dfs(dis[i]);
		siz[x]+=siz[dis[i]];
		if(siz[son[x]]<siz[dis[i]])son[x]=dis[i];
	}
}
il vd dfs(int x,int tp){
	top[x]=tp;if(son[x])dfs(son[x],tp);
	for(int i=fir[x];i;i=nxt[i])if(fa[x]!=dis[i]&&son[x]!=dis[i])dfs(dis[i],dis[i]);
}
il int LCA(int a,int b){
	while(top[a]^top[b])
		if(dep[top[a]]>dep[top[b]])a=fa[top[a]];
		else b=fa[top[b]];
	return dep[a]>dep[b]?b:a;
}
ll ans[100010];
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	n=gi();int Q=gi();
	for(int i=1;i<n;++i)pa[i]=gi(),pb[i]=gi(),pc[i]=gi(),pd[i]=gi(),link(pa[i],pb[i],pd[i]),link(pb[i],pa[i],pd[i]),Ge[pc[i]].push_back(i);
	for(int i=1;i<=Q;++i)qx[i]=gi(),qy[i]=gi(),qu[i]=gi(),qv[i]=gi(),Gq[qx[i]].push_back(i);
	dfs(1);dfs(1,1);
	for(int i=1;i<n;++i)if(pb[i]==fa[pa[i]])std::swap(pa[i],pb[i]);
	for(int i=1;i<=Q;++i)ans[i]=dist[qu[i]]+dist[qv[i]]-2*dist[LCA(qu[i],qv[i])];
	for(int i=1;i<n;++i){
		for(int j:Ge[i])update(t1,dfn[pb[j]],1),update(t1,dfn[pb[j]]+siz[pb[j]],-1);
		for(int j:Ge[i])update(t2,dfn[pb[j]],pd[j]),update(t2,dfn[pb[j]]+siz[pb[j]],-pd[j]);
		for(int j:Gq[i]){
			int a=qu[j],b=qv[j],c=LCA(a,b);
			ans[j]-=query(t2,dfn[a])+query(t2,dfn[b])-2*query(t2,dfn[c]);
			ans[j]+=qy[j]*(query(t1,dfn[a])+query(t1,dfn[b])-2*query(t1,dfn[c]));
		}
		for(int j:Ge[i])update(t1,dfn[pb[j]],-1),update(t1,dfn[pb[j]]+siz[pb[j]],1);
		for(int j:Ge[i])update(t2,dfn[pb[j]],-pd[j]),update(t2,dfn[pb[j]]+siz[pb[j]],pd[j]);
	}
	for(int i=1;i<=Q;++i)printf("%lld\n",ans[i]);
	return 0;
}

```