#include<bits/stdc++.h>
#define uLL unsigned long long
using namespace std;
#define LL long long
#define N 200005
#define M 4000005
#define int LL
struct xx {
	int ed,last,ci,di;
} w[N<<1];
int cot = 0,head[N];
void Add(int s,int e,int c,int d) {
	w[++cot].ed = e,w[cot].last = head[s],head[s] = cot;
	w[cot].ci = c,w[cot].di = d;
	return ;
}


int lc[M],rc[M],rt[N<<1],sum[M],num[M],tot;
void Build(int &rt,int L,int R) {
	rt = ++tot;
	if(L == R) return ;
	int mid = L+R>>1;
	Build(lc[rt],L,mid);
	Build(rc[rt],mid+1,R);
	return ;
}
int idx;
int Update(int pre,int L,int R,int d) {
	int rt = ++tot;
	lc[rt] = lc[pre],rc[rt] = rc[pre],sum[rt] = sum[pre]+d,num[rt] = num[pre]+1;
	if(L == R) return rt;
	int mid = L+R>>1;
	if(idx <= mid) lc[rt] = Update(lc[rt],L,mid,d);
	else rc[rt] = Update(rc[rt],mid+1,R,d);
	return rt;
}
int dep[N],fa[N][23],n,Q;
void dfs(int now,int pre,int c,int d) {
	dep[now] = dep[pre]+1,fa[now][0] = pre;
	if(now == 1) rt[now] = rt[pre];
	else {
		idx = c;
		rt[now] = Update(rt[pre],1,n,d);
	}
	for(int i=head[now]; i; i=w[i].last) {
		int e = w[i].ed;
		if(e == pre) continue;
		dfs(e,now,w[i].ci,w[i].di);
	}
	return ;
}

int Up(int x,int step) {
	for(int i=0; i<=20; i++) {
		if( (step&(1<<i)) ) x = fa[x][i];
	}
	return x;
}

int Lca(int a,int b) {
	if(dep[a] > dep[b]) swap(a,b);
	b = Up(b,dep[b]-dep[a]);
	if(a == b) return a;
	for(int i=20; i>=0; i--) {
		if(fa[a][i] != fa[b][i])
			a = fa[a][i],b = fa[b][i];
	}
	return fa[a][0];
}

int Query_1(int T1,int T2,int T3,int T4,int L,int R) {
	if(L == R) return sum[T1]+sum[T2]-sum[T3]-sum[T4];
	int mid = L + R>>1;
	if(idx <= mid) return Query_1(lc[T1],lc[T2],lc[T3],lc[T4],L,mid);
	else return Query_1(rc[T1],rc[T2],rc[T3],rc[T4],mid+1,R);
}


int Query_2(int T1,int T2,int T3,int T4,int L,int R) {
	if(L == R) return num[T1]+num[T2]-num[T3]-num[T4];
	int mid = L + R>>1;
	if(idx <= mid) return Query_2(lc[T1],lc[T2],lc[T3],lc[T4],L,mid);
	else return Query_2(rc[T1],rc[T2],rc[T3],rc[T4],mid+1,R);
}

signed main() {
	cin >> n >> Q;
	for(int i=1,a,b,c,d; i<n; i++) {
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		Add(a,b,c,d);
		Add(b,a,c,d);
	}
	Build(rt[0],1,n);
	dfs(1,0,0,0);
	for(int j=1; j<=20; j++) {
		for(int i=1; i<=n; i++) fa[i][j] = fa[fa[i][j-1]][j-1];
	}
	int x,y,u,v;
	while(Q--) {
		scanf("%lld%lld%lld%lld",&x,&y,&u,&v);
		int LCA = Lca(u,v);
		LL he = sum[rt[u]]+sum[rt[v]] - sum[rt[LCA]] - sum[rt[LCA]];
		idx = x;
		he -= Query_1(rt[u],rt[v],rt[LCA],rt[LCA],1,n);
		int h = Query_2(rt[u],rt[v],rt[LCA],rt[LCA],1,n);
		he += h*y;
		printf("%lld\n",he);
	}
	return 0;
}
### Prompt

Your challenge is to write 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>
#define uLL unsigned long long
using namespace std;
#define LL long long
#define N 200005
#define M 4000005
#define int LL
struct xx {
	int ed,last,ci,di;
} w[N<<1];
int cot = 0,head[N];
void Add(int s,int e,int c,int d) {
	w[++cot].ed = e,w[cot].last = head[s],head[s] = cot;
	w[cot].ci = c,w[cot].di = d;
	return ;
}


int lc[M],rc[M],rt[N<<1],sum[M],num[M],tot;
void Build(int &rt,int L,int R) {
	rt = ++tot;
	if(L == R) return ;
	int mid = L+R>>1;
	Build(lc[rt],L,mid);
	Build(rc[rt],mid+1,R);
	return ;
}
int idx;
int Update(int pre,int L,int R,int d) {
	int rt = ++tot;
	lc[rt] = lc[pre],rc[rt] = rc[pre],sum[rt] = sum[pre]+d,num[rt] = num[pre]+1;
	if(L == R) return rt;
	int mid = L+R>>1;
	if(idx <= mid) lc[rt] = Update(lc[rt],L,mid,d);
	else rc[rt] = Update(rc[rt],mid+1,R,d);
	return rt;
}
int dep[N],fa[N][23],n,Q;
void dfs(int now,int pre,int c,int d) {
	dep[now] = dep[pre]+1,fa[now][0] = pre;
	if(now == 1) rt[now] = rt[pre];
	else {
		idx = c;
		rt[now] = Update(rt[pre],1,n,d);
	}
	for(int i=head[now]; i; i=w[i].last) {
		int e = w[i].ed;
		if(e == pre) continue;
		dfs(e,now,w[i].ci,w[i].di);
	}
	return ;
}

int Up(int x,int step) {
	for(int i=0; i<=20; i++) {
		if( (step&(1<<i)) ) x = fa[x][i];
	}
	return x;
}

int Lca(int a,int b) {
	if(dep[a] > dep[b]) swap(a,b);
	b = Up(b,dep[b]-dep[a]);
	if(a == b) return a;
	for(int i=20; i>=0; i--) {
		if(fa[a][i] != fa[b][i])
			a = fa[a][i],b = fa[b][i];
	}
	return fa[a][0];
}

int Query_1(int T1,int T2,int T3,int T4,int L,int R) {
	if(L == R) return sum[T1]+sum[T2]-sum[T3]-sum[T4];
	int mid = L + R>>1;
	if(idx <= mid) return Query_1(lc[T1],lc[T2],lc[T3],lc[T4],L,mid);
	else return Query_1(rc[T1],rc[T2],rc[T3],rc[T4],mid+1,R);
}


int Query_2(int T1,int T2,int T3,int T4,int L,int R) {
	if(L == R) return num[T1]+num[T2]-num[T3]-num[T4];
	int mid = L + R>>1;
	if(idx <= mid) return Query_2(lc[T1],lc[T2],lc[T3],lc[T4],L,mid);
	else return Query_2(rc[T1],rc[T2],rc[T3],rc[T4],mid+1,R);
}

signed main() {
	cin >> n >> Q;
	for(int i=1,a,b,c,d; i<n; i++) {
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		Add(a,b,c,d);
		Add(b,a,c,d);
	}
	Build(rt[0],1,n);
	dfs(1,0,0,0);
	for(int j=1; j<=20; j++) {
		for(int i=1; i<=n; i++) fa[i][j] = fa[fa[i][j-1]][j-1];
	}
	int x,y,u,v;
	while(Q--) {
		scanf("%lld%lld%lld%lld",&x,&y,&u,&v);
		int LCA = Lca(u,v);
		LL he = sum[rt[u]]+sum[rt[v]] - sum[rt[LCA]] - sum[rt[LCA]];
		idx = x;
		he -= Query_1(rt[u],rt[v],rt[LCA],rt[LCA],1,n);
		int h = Query_2(rt[u],rt[v],rt[LCA],rt[LCA],1,n);
		he += h*y;
		printf("%lld\n",he);
	}
	return 0;
}
```