#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
int n, q, a, b, c, d, kk = 1;
vector<vector<tuple<int,int,int>>> G, cl;
vector<int> in, head, par, dis;
int dfs1(int p, int u){
	int ret = 1, tmax = 0, temp;
	par[u] = p;
	for(auto &nx: G[u])if(get<0>(nx) != p){
		dis[get<0>(nx)] = dis[u] + get<2>(nx);
		ret += temp = dfs1(u,get<0>(nx));
		if(temp > tmax){
			swap(G[u][0], nx);
			tmax = temp;
		}
	}
	return ret;
}
void dfs2(int p, int u){
	in[u] = kk++;
	head[u] = p != -1 && get<0>(G[p][0]) == u ? head[p] : u;
	for(auto &nx: G[u])if(get<0>(nx) != p){
		cl[get<1>(nx)].push_back(make_tuple(kk,1,get<2>(nx)));
		dfs2(u,get<0>(nx));
		cl[get<1>(nx)].push_back(make_tuple(kk-1,-1,-get<2>(nx)));
	}
	kk++;
}
void color(){
	for(auto &it: cl){
		for(int i = 1; i < it.size(); i++){
			get<1>(it[i]) += get<1>(it[i-1]);
			get<2>(it[i]) += get<2>(it[i-1]);
		}
	}
}
int lca(int a, int b){
	while(head[a] != head[b]){
		if(in[a] < in[b]) swap(a,b);
		a = par[head[a]];
	}
	return in[a] < in[b] ? a : b;
}
int query(int a, int b, int c, int d){
	int e = lca(c,d), ret = dis[c] + dis[d] - dis[e]*2;
	int u[3] = {c,d,e};
	rep(i,3){
		int cc, dd;
		tie(ignore, cc, dd) = *--lower_bound(cl[a].begin(), cl[a].end(), make_tuple(in[u[i]]+1,0,0));
		ret += (cc*b - dd) * (i == 2 ? -2 : 1);
	}
	return ret;
}
int main(){
	scanf("%d%d", &n, &q);
	G.resize(n); cl.assign(n,{make_tuple(0,0,0)}); in.resize(n); head.resize(n); par.resize(n); dis.resize(n);
	rep(i,n-1){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--;b--;c--;
		G[a].push_back(make_tuple(b,c,d));
		G[b].push_back(make_tuple(a,c,d));
	}
	dis[0] = 0; dfs1(-1,0); dfs2(-1,0);
	color();
	rep(i,q){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--;c--;d--;
		printf("%d\n", query(a,b,c,d));
	}
}
### 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<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
int n, q, a, b, c, d, kk = 1;
vector<vector<tuple<int,int,int>>> G, cl;
vector<int> in, head, par, dis;
int dfs1(int p, int u){
	int ret = 1, tmax = 0, temp;
	par[u] = p;
	for(auto &nx: G[u])if(get<0>(nx) != p){
		dis[get<0>(nx)] = dis[u] + get<2>(nx);
		ret += temp = dfs1(u,get<0>(nx));
		if(temp > tmax){
			swap(G[u][0], nx);
			tmax = temp;
		}
	}
	return ret;
}
void dfs2(int p, int u){
	in[u] = kk++;
	head[u] = p != -1 && get<0>(G[p][0]) == u ? head[p] : u;
	for(auto &nx: G[u])if(get<0>(nx) != p){
		cl[get<1>(nx)].push_back(make_tuple(kk,1,get<2>(nx)));
		dfs2(u,get<0>(nx));
		cl[get<1>(nx)].push_back(make_tuple(kk-1,-1,-get<2>(nx)));
	}
	kk++;
}
void color(){
	for(auto &it: cl){
		for(int i = 1; i < it.size(); i++){
			get<1>(it[i]) += get<1>(it[i-1]);
			get<2>(it[i]) += get<2>(it[i-1]);
		}
	}
}
int lca(int a, int b){
	while(head[a] != head[b]){
		if(in[a] < in[b]) swap(a,b);
		a = par[head[a]];
	}
	return in[a] < in[b] ? a : b;
}
int query(int a, int b, int c, int d){
	int e = lca(c,d), ret = dis[c] + dis[d] - dis[e]*2;
	int u[3] = {c,d,e};
	rep(i,3){
		int cc, dd;
		tie(ignore, cc, dd) = *--lower_bound(cl[a].begin(), cl[a].end(), make_tuple(in[u[i]]+1,0,0));
		ret += (cc*b - dd) * (i == 2 ? -2 : 1);
	}
	return ret;
}
int main(){
	scanf("%d%d", &n, &q);
	G.resize(n); cl.assign(n,{make_tuple(0,0,0)}); in.resize(n); head.resize(n); par.resize(n); dis.resize(n);
	rep(i,n-1){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--;b--;c--;
		G[a].push_back(make_tuple(b,c,d));
		G[b].push_back(make_tuple(a,c,d));
	}
	dis[0] = 0; dfs1(-1,0); dfs2(-1,0);
	color();
	rep(i,q){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--;c--;d--;
		printf("%d\n", query(a,b,c,d));
	}
}
```