#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define inf1 1e18+1
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 100005
#define mid(l,r) l+(r-l)/2
using namespace std;
ll gcd(ll a,ll b){ if(a>b)swap(a,b);if(!a)return b;return gcd(b%a,a);}
int n,k,q;
int tin[N],tout[N],tim,num,sum;
int up[N][20],ls[N*20],rs[N*20],Root[N],mark,cnt[N*20],tot[N*20];
struct edge{
	ll int u,v,c,w;
	edge(){}
	edge(int a,int b,int c,int d){u=a;v=b;this->c=c;w=d;}
};
vector<int>ed[N];
int dis[N];
edge edg[N];
void addnode(int &i,int pa,int l,int r,int c,int w){
	i=++mark;
	cnt[i]=cnt[pa]+1;
	tot[i]=tot[pa]+w;
	ls[i]=ls[pa];
	rs[i]=rs[pa];
	if(l==r)return;
	if(c<=mid(l,r))addnode(ls[i],ls[pa],l,mid(l,r),c,w);
	else addnode(rs[i],rs[pa],mid(l,r)+1,r,c,w);
}
void qry(int i,int l,int r,int c){
	//if(c>r||c<l)return;
	if(l==r){
		num=cnt[i];
		sum=tot[i];
		return;
	}
	if(c<=mid(l,r))qry(ls[i],l,mid(l,r),c);
	else qry(rs[i],mid(l,r)+1,r,c);
}
void dfs(int i,int p,ll ww){
	tin[i]=++tim;
	dis[i]=dis[p]+ww;
	up[i][0]=p;
	for(int j=1;j<=k;j++)up[i][j]=up[up[i][j-1]][j-1];
	for(int j:ed[i]){
		int v=edg[j].u+edg[j].v-i;
		if(v==p)continue;
		addnode(Root[v],Root[i],0,n-1,edg[j].c,edg[j].w);
		dfs(v,i,edg[j].w);
	}
	tout[i]=++tim;
}
bool isan(int i,int j){
	return tin[i]<=tin[j]&&tout[i]>=tout[j];
}
int lca(int i,int j){
	if(isan(i,j))return i;
	if(isan(j,i))return j;
	for(int k1=k;k1>=0;k1--){
		if(!isan(up[i][k1],j))i=up[i][k1];
	}
	return up[i][0];
}
void solve(){
	cin>>n>>q;
	k=log2(n)+1;
	for(int i=0;i<n-1;i++){
		ll int u,v,c,w;
		cin>>u>>v>>c>>w;
		edg[i]=edge(u,v,c,w);
		ed[u].pb(i);
		ed[v].pb(i);
	}
	tin[0]=++tim;
	dfs(1,0,0);
	tout[0]=++tim;
	while(q--){
		ll u,v,c,w;
		cin>>c>>w>>u>>v;
		int l=lca(u,v);
		qry(Root[u],0,n-1,c);
		int a1=num,b1=sum;
		qry(Root[v],0,n-1,c);
		int a2=num,b2=sum;
		qry(Root[l],0,n-1,c);
		int a3=a1+a2-2*num,b3=b1+b2-2*sum;
		cout<<dis[u]+dis[v]-2*dis[l]-b3+a3*w<<"\n";
	}
}
int main()
{
	waste;
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}
### Prompt

Your task is to create 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<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define inf1 1e18+1
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 100005
#define mid(l,r) l+(r-l)/2
using namespace std;
ll gcd(ll a,ll b){ if(a>b)swap(a,b);if(!a)return b;return gcd(b%a,a);}
int n,k,q;
int tin[N],tout[N],tim,num,sum;
int up[N][20],ls[N*20],rs[N*20],Root[N],mark,cnt[N*20],tot[N*20];
struct edge{
	ll int u,v,c,w;
	edge(){}
	edge(int a,int b,int c,int d){u=a;v=b;this->c=c;w=d;}
};
vector<int>ed[N];
int dis[N];
edge edg[N];
void addnode(int &i,int pa,int l,int r,int c,int w){
	i=++mark;
	cnt[i]=cnt[pa]+1;
	tot[i]=tot[pa]+w;
	ls[i]=ls[pa];
	rs[i]=rs[pa];
	if(l==r)return;
	if(c<=mid(l,r))addnode(ls[i],ls[pa],l,mid(l,r),c,w);
	else addnode(rs[i],rs[pa],mid(l,r)+1,r,c,w);
}
void qry(int i,int l,int r,int c){
	//if(c>r||c<l)return;
	if(l==r){
		num=cnt[i];
		sum=tot[i];
		return;
	}
	if(c<=mid(l,r))qry(ls[i],l,mid(l,r),c);
	else qry(rs[i],mid(l,r)+1,r,c);
}
void dfs(int i,int p,ll ww){
	tin[i]=++tim;
	dis[i]=dis[p]+ww;
	up[i][0]=p;
	for(int j=1;j<=k;j++)up[i][j]=up[up[i][j-1]][j-1];
	for(int j:ed[i]){
		int v=edg[j].u+edg[j].v-i;
		if(v==p)continue;
		addnode(Root[v],Root[i],0,n-1,edg[j].c,edg[j].w);
		dfs(v,i,edg[j].w);
	}
	tout[i]=++tim;
}
bool isan(int i,int j){
	return tin[i]<=tin[j]&&tout[i]>=tout[j];
}
int lca(int i,int j){
	if(isan(i,j))return i;
	if(isan(j,i))return j;
	for(int k1=k;k1>=0;k1--){
		if(!isan(up[i][k1],j))i=up[i][k1];
	}
	return up[i][0];
}
void solve(){
	cin>>n>>q;
	k=log2(n)+1;
	for(int i=0;i<n-1;i++){
		ll int u,v,c,w;
		cin>>u>>v>>c>>w;
		edg[i]=edge(u,v,c,w);
		ed[u].pb(i);
		ed[v].pb(i);
	}
	tin[0]=++tim;
	dfs(1,0,0);
	tout[0]=++tim;
	while(q--){
		ll u,v,c,w;
		cin>>c>>w>>u>>v;
		int l=lca(u,v);
		qry(Root[u],0,n-1,c);
		int a1=num,b1=sum;
		qry(Root[v],0,n-1,c);
		int a2=num,b2=sum;
		qry(Root[l],0,n-1,c);
		int a3=a1+a2-2*num,b3=b1+b2-2*sum;
		cout<<dis[u]+dis[v]-2*dis[l]-b3+a3*w<<"\n";
	}
}
int main()
{
	waste;
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}
```