#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int P=1e9+7;
const int M=1e5+5;
int head[M],to[M<<1],val[M<<1],nxt[M<<1],col[M<<1],tot;
void Add(int x,int y,int c,int d){
	to[++tot]=y;
	nxt[tot]=head[x];
	col[tot]=c,val[tot]=d;
	head[x]=tot;
}
int n,m;
int rt[M];
struct node{int cnt,sum;};
struct Seg{
	#define N M*40
	int Lson[N],Rson[N],cnt[N],sum[N],tot;
	void insert(int &rt,int od,int L,int R,int k,int x){
		rt=++tot;
		sum[rt]=sum[od],cnt[rt]=cnt[od];
		Lson[rt]=Lson[od],Rson[rt]=Rson[od];
		if(L==R){cnt[rt]++,sum[rt]+=x;return;}
		int mid=(L+R)>>1;
		if(k<=mid)insert(Lson[rt],Lson[od],L,mid,k,x);
		else insert(Rson[rt],Rson[od],mid+1,R,k,x);
	}
	node query(int rt,int L,int R,int k){
		if(!rt)return (node){0,0};
		if(L==R)return (node){cnt[rt],sum[rt]};
		int mid=(L+R)>>1;
		if(k<=mid)return query(Lson[rt],L,mid,k);
		else return query(Rson[rt],mid+1,R,k);
	}
}tree;

int top[M],son[M],fa[M],sz[M],dep[M],dis[M];

void dfs(int x,int f){
	sz[x]=1,son[x]=0;
	fa[x]=f,dep[x]=dep[f]+1;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==f)continue;
		dis[y]=dis[x]+val[i];
		tree.insert(rt[y],rt[x],1,n,col[i],val[i]);
		dfs(y,x);
		sz[x]+=sz[y];
		if(sz[y]>sz[son[x]])son[x]=y;
	}
}
void dfs_top(int x,int f,int tp){
	top[x]=tp;
	if(son[x])dfs_top(son[x],x,tp);
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==f||y==son[x])continue;
		dfs_top(y,x,y);
	}
}
int LCA(int a,int b) {
	while(top[a]!=top[b]) {
		if(dep[top[a]]>dep[top[b]])swap(a,b);
		b=fa[top[b]];
	}
	return dep[a]<dep[b]?a:b;
}
void solve(){
	for(int i=1,x,d,u,v;i<=m;i++){
		scanf("%d%d%d%d",&x,&d,&u,&v);
		int lca=LCA(u,v);
		int sum=dis[u]+dis[v]-2*dis[lca];
		node t1=tree.query(rt[u],1,n,x);
		node t2=tree.query(rt[v],1,n,x);
		node t3=tree.query(rt[lca],1,n,x);
		sum-=(t1.sum+t2.sum-t3.sum*2);
		sum+=(t1.cnt+t2.cnt-t3.cnt*2)*d;
		printf("%d\n",sum);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,c,d;i<n;i++){
		scanf("%d%d%d%d",&x,&y,&c,&d);
		Add(x,y,c,d),Add(y,x,c,d);
	}
	dfs(1,0),dfs_top(1,0,1);
	solve();
	return 0;
}
### Prompt

Please formulate 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 ll long long
const int P=1e9+7;
const int M=1e5+5;
int head[M],to[M<<1],val[M<<1],nxt[M<<1],col[M<<1],tot;
void Add(int x,int y,int c,int d){
	to[++tot]=y;
	nxt[tot]=head[x];
	col[tot]=c,val[tot]=d;
	head[x]=tot;
}
int n,m;
int rt[M];
struct node{int cnt,sum;};
struct Seg{
	#define N M*40
	int Lson[N],Rson[N],cnt[N],sum[N],tot;
	void insert(int &rt,int od,int L,int R,int k,int x){
		rt=++tot;
		sum[rt]=sum[od],cnt[rt]=cnt[od];
		Lson[rt]=Lson[od],Rson[rt]=Rson[od];
		if(L==R){cnt[rt]++,sum[rt]+=x;return;}
		int mid=(L+R)>>1;
		if(k<=mid)insert(Lson[rt],Lson[od],L,mid,k,x);
		else insert(Rson[rt],Rson[od],mid+1,R,k,x);
	}
	node query(int rt,int L,int R,int k){
		if(!rt)return (node){0,0};
		if(L==R)return (node){cnt[rt],sum[rt]};
		int mid=(L+R)>>1;
		if(k<=mid)return query(Lson[rt],L,mid,k);
		else return query(Rson[rt],mid+1,R,k);
	}
}tree;

int top[M],son[M],fa[M],sz[M],dep[M],dis[M];

void dfs(int x,int f){
	sz[x]=1,son[x]=0;
	fa[x]=f,dep[x]=dep[f]+1;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==f)continue;
		dis[y]=dis[x]+val[i];
		tree.insert(rt[y],rt[x],1,n,col[i],val[i]);
		dfs(y,x);
		sz[x]+=sz[y];
		if(sz[y]>sz[son[x]])son[x]=y;
	}
}
void dfs_top(int x,int f,int tp){
	top[x]=tp;
	if(son[x])dfs_top(son[x],x,tp);
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==f||y==son[x])continue;
		dfs_top(y,x,y);
	}
}
int LCA(int a,int b) {
	while(top[a]!=top[b]) {
		if(dep[top[a]]>dep[top[b]])swap(a,b);
		b=fa[top[b]];
	}
	return dep[a]<dep[b]?a:b;
}
void solve(){
	for(int i=1,x,d,u,v;i<=m;i++){
		scanf("%d%d%d%d",&x,&d,&u,&v);
		int lca=LCA(u,v);
		int sum=dis[u]+dis[v]-2*dis[lca];
		node t1=tree.query(rt[u],1,n,x);
		node t2=tree.query(rt[v],1,n,x);
		node t3=tree.query(rt[lca],1,n,x);
		sum-=(t1.sum+t2.sum-t3.sum*2);
		sum+=(t1.cnt+t2.cnt-t3.cnt*2)*d;
		printf("%d\n",sum);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,c,d;i<n;i++){
		scanf("%d%d%d%d",&x,&y,&c,&d);
		Add(x,y,c,d),Add(y,x,c,d);
	}
	dfs(1,0),dfs_top(1,0,1);
	solve();
	return 0;
}
```