#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, ll> P;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int n,db[100100][20],cnt=0,dp[100100],id[100100];
bool visited[100100];
vector<P> path[225816];

struct edge{
	int to,c;
	ll d;
};

vector<edge> g[100100];

void dfs(int v, int p=0){
	int i;
	edge e;
	visited[v] = true;
	dp[v] = dp[p]+1;
	db[v][0] = p;
	id[v] = cnt; ++cnt;
	// cout << v << " ";
	for(i=(g[v].l_ength()-1); i>=0; --i){
		e = g[v][i];
		if(visited[e.to]){
			continue;
		}
		path[0].push_back(P(cnt,e.d));
		path[e.c].push_back(P(cnt,e.d));
		path[e.c+n].push_back(P(cnt,1ll));
		// cout << "( " << v << "->" << e.to << ") ";
		dfs(e.to,v);
		path[0].push_back(P(cnt,-e.d));
		path[e.c].push_back(P(cnt,-e.d));
		path[e.c+n].push_back(P(cnt,-1ll));
		// cout << "( " << e.to << "->" << v << ") ";
	}
}

int lca(int u, int v){
	int d = 0,i;
	d = dp[u] - dp[v];
	if(d < 0){
		swap(u,v);
		d = (-d);
	}
	for(i=0; i<20; ++i){
		if(d&(1<<i)){
			u = db[u][i];
		}
	}
	if(u==v){
		return u;
	}
	for(i=19; i>=0; --i){
		if(db[u][i] == db[v][i]){
			continue;
		}
		u = db[u][i];
		v = db[v][i];
	}
	return db[u][0];
}

ll query(int c, int v){
	int l,r,m;
	v = id[v];
	l = 0; r = path[c].l_ength();
	while(r-l>1){
		m = ((l+r)>>1);
		if(path[c][m].first > v){
			r = m;
		}else{
			l = m;
		}
	}
	return path[c][l].second;
}

int main(void){
	int q,i,j,x,a,b,c;
	ll d,y,ans;
	edge e;
	cin >> n >> q;
	for(i=1; i<n; ++i){
		cin >> a >> b >> e.c >> e.d; --a; --b;
		e.to = b; g[a].push_back(e);
		e.to = a; g[b].push_back(e);
	}
	for(j=0; j<n*2; ++j){
		path[j].push_back(P(-1,0ll));
	}
	dp[0] = -1; dfs(0); // cout << endl;
	for(j=1; j<20; ++j){
		for(i=0; i<n; ++i){
			db[i][j] = db[db[i][j-1]][j-1];
		}
	}
	for(j=0; j<n*2; ++j){
		for(i=1; i<path[j].l_ength(); ++i){
			path[j][i].second += path[j][i-1].second;
		}
	}
	for(i=0; i<q; ++i){
		cin >> x >> y >> a >> b; --a; --b;
		c = lca(a,b);
		ans = query(x+n,a)+query(x+n,b)-query(x+n,c)*2;
		ans *= y;
		ans -= query(x,a)+query(x,b)-query(x,c)*2;
		ans += query(0,a)+query(0,b)-query(0,c)*2;
		cout << ans << endl;
	}
	return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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"
using namespace std;
typedef long long ll;
typedef pair<int, ll> P;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int n,db[100100][20],cnt=0,dp[100100],id[100100];
bool visited[100100];
vector<P> path[225816];

struct edge{
	int to,c;
	ll d;
};

vector<edge> g[100100];

void dfs(int v, int p=0){
	int i;
	edge e;
	visited[v] = true;
	dp[v] = dp[p]+1;
	db[v][0] = p;
	id[v] = cnt; ++cnt;
	// cout << v << " ";
	for(i=(g[v].l_ength()-1); i>=0; --i){
		e = g[v][i];
		if(visited[e.to]){
			continue;
		}
		path[0].push_back(P(cnt,e.d));
		path[e.c].push_back(P(cnt,e.d));
		path[e.c+n].push_back(P(cnt,1ll));
		// cout << "( " << v << "->" << e.to << ") ";
		dfs(e.to,v);
		path[0].push_back(P(cnt,-e.d));
		path[e.c].push_back(P(cnt,-e.d));
		path[e.c+n].push_back(P(cnt,-1ll));
		// cout << "( " << e.to << "->" << v << ") ";
	}
}

int lca(int u, int v){
	int d = 0,i;
	d = dp[u] - dp[v];
	if(d < 0){
		swap(u,v);
		d = (-d);
	}
	for(i=0; i<20; ++i){
		if(d&(1<<i)){
			u = db[u][i];
		}
	}
	if(u==v){
		return u;
	}
	for(i=19; i>=0; --i){
		if(db[u][i] == db[v][i]){
			continue;
		}
		u = db[u][i];
		v = db[v][i];
	}
	return db[u][0];
}

ll query(int c, int v){
	int l,r,m;
	v = id[v];
	l = 0; r = path[c].l_ength();
	while(r-l>1){
		m = ((l+r)>>1);
		if(path[c][m].first > v){
			r = m;
		}else{
			l = m;
		}
	}
	return path[c][l].second;
}

int main(void){
	int q,i,j,x,a,b,c;
	ll d,y,ans;
	edge e;
	cin >> n >> q;
	for(i=1; i<n; ++i){
		cin >> a >> b >> e.c >> e.d; --a; --b;
		e.to = b; g[a].push_back(e);
		e.to = a; g[b].push_back(e);
	}
	for(j=0; j<n*2; ++j){
		path[j].push_back(P(-1,0ll));
	}
	dp[0] = -1; dfs(0); // cout << endl;
	for(j=1; j<20; ++j){
		for(i=0; i<n; ++i){
			db[i][j] = db[db[i][j-1]][j-1];
		}
	}
	for(j=0; j<n*2; ++j){
		for(i=1; i<path[j].l_ength(); ++i){
			path[j][i].second += path[j][i-1].second;
		}
	}
	for(i=0; i<q; ++i){
		cin >> x >> y >> a >> b; --a; --b;
		c = lca(a,b);
		ans = query(x+n,a)+query(x+n,b)-query(x+n,c)*2;
		ans *= y;
		ans -= query(x,a)+query(x,b)-query(x,c)*2;
		ans += query(0,a)+query(0,b)-query(0,c)*2;
		cout << ans << endl;
	}
	return 0;
}

```