#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define clr(x,y) memset(x,y,sizeof(x))
#define in(a) a=read()
#define out(a) printf("%d\n",a)
inline ll read(){
    char c=getchar();ll f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return x*f;
}
#define mod 1000000007
void MOD(int &x){if(x>=mod)x-=mod;}
#define maxn 100010
#define inf (1<<30)
int l,nxt[maxn*2],head[maxn],to[maxn*2],cl[maxn*2],v[maxn*2];
void add(int x,int y,int c,int z){
	l++;nxt[l]=head[x];head[x]=l;to[l]=y;cl[l]=c;v[l]=z;
}
int bin[maxn];
int fa[maxn][30],d[maxn],s[maxn];
void dfs(int x){
	FOR(i,1,20)fa[x][i]=fa[fa[x][i-1]][i-1];
	FORL(i,x){
		int c=to[i];
		if(c==fa[x][0])continue;
		fa[c][0]=x;d[c]=d[x]+1;s[c]=s[x]+v[i];
		dfs(c);
	}
}
int lca(int x,int y){
	if(d[x]<d[y])swap(x,y);
	int k=d[x]-d[y];
	FOR(i,0,20)
		if(k&(1<<i))
			x=fa[x][i];
	if(x==y)return x;
	FORD(i,20,0)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return x==y?x:fa[x][0];
}
struct A{
	int cl,v,c,id;
};
#include<vector>
vector<A>ve[maxn];
int ans[maxn];
int sz[maxn],sum[maxn];
void dfs2(int x){
	int l=ve[x].size();
	FOR(i,0,l-1){
		A q=ve[x][i];
		ans[q.id]-=q.c*sum[q.cl];
		ans[q.id]+=q.c*sz[q.cl]*q.v;
	}
	FORL(i,x){
		int c=to[i];
		if(c==fa[x][0])continue;
		sum[cl[i]]+=v[i];
		sz[cl[i]]++;
		dfs2(c); 
		sum[cl[i]]-=v[i];
		sz[cl[i]]--;
	}
}
int main(){
	int n,m;
	in(n);in(m);
	FOR(i,2,n)bin[i]=bin[i/2]+1;
	FOR(i,1,n-1){
		int x,y,C,D;
		in(x);in(y);in(C);in(D);
		add(x,y,C,D);add(y,x,C,D); 
	}
	dfs(1);
	FOR(i,1,m){
		int x,y,u,v;
		in(x);in(y);in(u);in(v);
		int z=lca(u,v);
		ans[i]=s[u]+s[v]-2*s[z]; 
		ve[u].push_back((A){x,y,1,i});
		ve[v].push_back((A){x,y,1,i});
		ve[z].push_back((A){x,y,-2,i});
	}
	dfs2(1);
	FOR(i,1,m)out(ans[i]);
}
### Prompt

Please create a solution in Cpp 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<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define clr(x,y) memset(x,y,sizeof(x))
#define in(a) a=read()
#define out(a) printf("%d\n",a)
inline ll read(){
    char c=getchar();ll f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return x*f;
}
#define mod 1000000007
void MOD(int &x){if(x>=mod)x-=mod;}
#define maxn 100010
#define inf (1<<30)
int l,nxt[maxn*2],head[maxn],to[maxn*2],cl[maxn*2],v[maxn*2];
void add(int x,int y,int c,int z){
	l++;nxt[l]=head[x];head[x]=l;to[l]=y;cl[l]=c;v[l]=z;
}
int bin[maxn];
int fa[maxn][30],d[maxn],s[maxn];
void dfs(int x){
	FOR(i,1,20)fa[x][i]=fa[fa[x][i-1]][i-1];
	FORL(i,x){
		int c=to[i];
		if(c==fa[x][0])continue;
		fa[c][0]=x;d[c]=d[x]+1;s[c]=s[x]+v[i];
		dfs(c);
	}
}
int lca(int x,int y){
	if(d[x]<d[y])swap(x,y);
	int k=d[x]-d[y];
	FOR(i,0,20)
		if(k&(1<<i))
			x=fa[x][i];
	if(x==y)return x;
	FORD(i,20,0)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return x==y?x:fa[x][0];
}
struct A{
	int cl,v,c,id;
};
#include<vector>
vector<A>ve[maxn];
int ans[maxn];
int sz[maxn],sum[maxn];
void dfs2(int x){
	int l=ve[x].size();
	FOR(i,0,l-1){
		A q=ve[x][i];
		ans[q.id]-=q.c*sum[q.cl];
		ans[q.id]+=q.c*sz[q.cl]*q.v;
	}
	FORL(i,x){
		int c=to[i];
		if(c==fa[x][0])continue;
		sum[cl[i]]+=v[i];
		sz[cl[i]]++;
		dfs2(c); 
		sum[cl[i]]-=v[i];
		sz[cl[i]]--;
	}
}
int main(){
	int n,m;
	in(n);in(m);
	FOR(i,2,n)bin[i]=bin[i/2]+1;
	FOR(i,1,n-1){
		int x,y,C,D;
		in(x);in(y);in(C);in(D);
		add(x,y,C,D);add(y,x,C,D); 
	}
	dfs(1);
	FOR(i,1,m){
		int x,y,u,v;
		in(x);in(y);in(u);in(v);
		int z=lca(u,v);
		ans[i]=s[u]+s[v]-2*s[z]; 
		ve[u].push_back((A){x,y,1,i});
		ve[v].push_back((A){x,y,1,i});
		ve[z].push_back((A){x,y,-2,i});
	}
	dfs2(1);
	FOR(i,1,m)out(ans[i]);
}
```