/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5;
struct EDGE{int u,v,col,len;}edg[N+5];
struct QUERY{int col,id,mdy,tag;};
vector<int> lnk[N+5];
vector<QUERY> qry[N+5];
int fa[N+5][20],dep[N+5],ans[N+5];
int n,m;
void Process(int u,int pre){
	fa[u][0]=pre;dep[u]=dep[pre]+1;
	for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=0;i<lnk[u].size();i++){
		int v=edg[lnk[u][i]].u==u? edg[lnk[u][i]].v:edg[lnk[u][i]].u;
		if(v==pre) continue;
		Process(v,u);
	}
}
int totfar,colcnt[N+5],collen[N+5];
void DFS(int u,int pre){
	for(auto it : qry[u])
		ans[it.id]+=it.tag*(totfar-collen[it.col]+colcnt[it.col]*it.mdy);
	for(int i=0;i<lnk[u].size();i++){
		int v=edg[lnk[u][i]].u==u? edg[lnk[u][i]].v:edg[lnk[u][i]].u;
		if(v==pre) continue;
		totfar+=edg[lnk[u][i]].len;
		colcnt[edg[lnk[u][i]].col]++;
		collen[edg[lnk[u][i]].col]+=edg[lnk[u][i]].len;
		DFS(v,u);
		totfar-=edg[lnk[u][i]].len;
		colcnt[edg[lnk[u][i]].col]--;
		collen[edg[lnk[u][i]].col]-=edg[lnk[u][i]].len;
	}
}
int LCA(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=19;i>=0;i--)
		if(dep[fa[u][i]]>=dep[v])
			u=fa[u][i];
	if(u==v) return u;
	for(int i=19;i>=0;i--)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v,col,len;scanf("%d%d%d%d",&u,&v,&col,&len);
		edg[i]=(EDGE){u,v,col,len};
		lnk[u].push_back(i);lnk[v].push_back(i);
	}
	Process(1,0);
	for(int i=1;i<=m;i++){
		int u,v,col,len;
		scanf("%d%d%d%d",&col,&len,&u,&v);
		int lca=LCA(u,v);
		qry[u].push_back((QUERY){col,i,len,1});
		qry[v].push_back((QUERY){col,i,len,1});
		qry[lca].push_back((QUERY){col,i,len,-2});
	}
	DFS(1,0);
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}
### Prompt

Create a solution in CPP for 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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5;
struct EDGE{int u,v,col,len;}edg[N+5];
struct QUERY{int col,id,mdy,tag;};
vector<int> lnk[N+5];
vector<QUERY> qry[N+5];
int fa[N+5][20],dep[N+5],ans[N+5];
int n,m;
void Process(int u,int pre){
	fa[u][0]=pre;dep[u]=dep[pre]+1;
	for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=0;i<lnk[u].size();i++){
		int v=edg[lnk[u][i]].u==u? edg[lnk[u][i]].v:edg[lnk[u][i]].u;
		if(v==pre) continue;
		Process(v,u);
	}
}
int totfar,colcnt[N+5],collen[N+5];
void DFS(int u,int pre){
	for(auto it : qry[u])
		ans[it.id]+=it.tag*(totfar-collen[it.col]+colcnt[it.col]*it.mdy);
	for(int i=0;i<lnk[u].size();i++){
		int v=edg[lnk[u][i]].u==u? edg[lnk[u][i]].v:edg[lnk[u][i]].u;
		if(v==pre) continue;
		totfar+=edg[lnk[u][i]].len;
		colcnt[edg[lnk[u][i]].col]++;
		collen[edg[lnk[u][i]].col]+=edg[lnk[u][i]].len;
		DFS(v,u);
		totfar-=edg[lnk[u][i]].len;
		colcnt[edg[lnk[u][i]].col]--;
		collen[edg[lnk[u][i]].col]-=edg[lnk[u][i]].len;
	}
}
int LCA(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=19;i>=0;i--)
		if(dep[fa[u][i]]>=dep[v])
			u=fa[u][i];
	if(u==v) return u;
	for(int i=19;i>=0;i--)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v,col,len;scanf("%d%d%d%d",&u,&v,&col,&len);
		edg[i]=(EDGE){u,v,col,len};
		lnk[u].push_back(i);lnk[v].push_back(i);
	}
	Process(1,0);
	for(int i=1;i<=m;i++){
		int u,v,col,len;
		scanf("%d%d%d%d",&col,&len,&u,&v);
		int lca=LCA(u,v);
		qry[u].push_back((QUERY){col,i,len,1});
		qry[v].push_back((QUERY){col,i,len,1});
		qry[lca].push_back((QUERY){col,i,len,-2});
	}
	DFS(1,0);
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}
```