#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> G, C, D;
int par[100010][21], euler[200010], ve[100010], dep[100010];
vector<vector<int>> s, t, num;
bool looked[100010];

int dfs(int key, int now){
	looked[key]=1;
	ve[key]=now;
	int res=now;
	for(int i=0; i<G[key].size(); ++i){
		if(!looked[G[key][i]]){
			par[G[key][i]][0]=key;
			dep[G[key][i]]=dep[key]+1;
			euler[res+1]=euler[res]+D[key][i];
			int tb=t[C[key][i]].back()+D[key][i], nb=num[C[key][i]].back();
			s[C[key][i]].emplace_back(res+1);
			t[C[key][i]].emplace_back(tb);
			num[C[key][i]].emplace_back(nb+1);
			res=dfs(G[key][i], res+1);
			euler[res+1]=euler[res]-D[key][i];
			tb -= D[key][i];
			s[C[key][i]].emplace_back(res+1);
			t[C[key][i]].emplace_back(tb);
			num[C[key][i]].emplace_back(nb);
			++res;
		}
	}
	return res;
}

int dist(int key, int X, int Y){
	int ok=0, ng=s[X].size();
	while(ok+1<ng){
		int mid=(ok+ng)/2;
		if(s[X][mid]<=ve[key]) ok=mid;
		else ng=mid;
	}
	return euler[ve[key]]-t[X][ok]+num[X][ok]*Y;
}

int solve(int X, int Y, int U, int V){
	int ut=U, vt=V;
	if(dep[ut]<dep[vt]) swap(ut, vt);
	for(int i=20; i>=0; --i){
		if((dep[ut]-dep[vt])&(1<<i)){
			ut=par[ut][i];
		}
	}
	int lca;
	if(ut==vt) lca=ut;
	else{
		for(int i=20; i>=0; --i){
			if(par[ut][i]!=par[vt][i]){
				ut=par[ut][i];
				vt=par[vt][i];
			}
		}
		lca=par[ut][0];
	}
	int p=dist(lca, X, Y);
	return (dist(U, X, Y)-p)+(dist(V, X, Y)-p);
}

int main() {
	int N, Q;
	cin >> N >> Q;
	G.resize(N+1);
	C.resize(N+1);
	D.resize(N+1);
	for(int i=1; i<N; ++i){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		G[a].emplace_back(b);
		C[a].emplace_back(c);
		D[a].emplace_back(d);
		G[b].emplace_back(a);
		C[b].emplace_back(c);
		D[b].emplace_back(d);
	}
	par[1][0]=0;
	dep[1]=0;
	s.assign(N+1, {0});
	t.assign(N+1, {0});
	num.assign(N+1, {0});
	dfs(1, 0);
	for(int i=1; i<21; ++i){
		for(int j=1; j<=N; ++j) par[j][i]=par[par[j][i-1]][i-1];
	}
	for(int i=0; i<Q; ++i){
		int x, y, u, v;
		cin >> x >> y >> u >> v;
		cout << solve(x, y, u, v) << endl;
	}
	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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> G, C, D;
int par[100010][21], euler[200010], ve[100010], dep[100010];
vector<vector<int>> s, t, num;
bool looked[100010];

int dfs(int key, int now){
	looked[key]=1;
	ve[key]=now;
	int res=now;
	for(int i=0; i<G[key].size(); ++i){
		if(!looked[G[key][i]]){
			par[G[key][i]][0]=key;
			dep[G[key][i]]=dep[key]+1;
			euler[res+1]=euler[res]+D[key][i];
			int tb=t[C[key][i]].back()+D[key][i], nb=num[C[key][i]].back();
			s[C[key][i]].emplace_back(res+1);
			t[C[key][i]].emplace_back(tb);
			num[C[key][i]].emplace_back(nb+1);
			res=dfs(G[key][i], res+1);
			euler[res+1]=euler[res]-D[key][i];
			tb -= D[key][i];
			s[C[key][i]].emplace_back(res+1);
			t[C[key][i]].emplace_back(tb);
			num[C[key][i]].emplace_back(nb);
			++res;
		}
	}
	return res;
}

int dist(int key, int X, int Y){
	int ok=0, ng=s[X].size();
	while(ok+1<ng){
		int mid=(ok+ng)/2;
		if(s[X][mid]<=ve[key]) ok=mid;
		else ng=mid;
	}
	return euler[ve[key]]-t[X][ok]+num[X][ok]*Y;
}

int solve(int X, int Y, int U, int V){
	int ut=U, vt=V;
	if(dep[ut]<dep[vt]) swap(ut, vt);
	for(int i=20; i>=0; --i){
		if((dep[ut]-dep[vt])&(1<<i)){
			ut=par[ut][i];
		}
	}
	int lca;
	if(ut==vt) lca=ut;
	else{
		for(int i=20; i>=0; --i){
			if(par[ut][i]!=par[vt][i]){
				ut=par[ut][i];
				vt=par[vt][i];
			}
		}
		lca=par[ut][0];
	}
	int p=dist(lca, X, Y);
	return (dist(U, X, Y)-p)+(dist(V, X, Y)-p);
}

int main() {
	int N, Q;
	cin >> N >> Q;
	G.resize(N+1);
	C.resize(N+1);
	D.resize(N+1);
	for(int i=1; i<N; ++i){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		G[a].emplace_back(b);
		C[a].emplace_back(c);
		D[a].emplace_back(d);
		G[b].emplace_back(a);
		C[b].emplace_back(c);
		D[b].emplace_back(d);
	}
	par[1][0]=0;
	dep[1]=0;
	s.assign(N+1, {0});
	t.assign(N+1, {0});
	num.assign(N+1, {0});
	dfs(1, 0);
	for(int i=1; i<21; ++i){
		for(int j=1; j<=N; ++j) par[j][i]=par[par[j][i-1]][i-1];
	}
	for(int i=0; i<Q; ++i){
		int x, y, u, v;
		cin >> x >> y >> u >> v;
		cout << solve(x, y, u, v) << endl;
	}
	return 0;
}
```