#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=2.5e5+7;
const int LogN=35;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int c[N],d[N],head[N],n,q,tot;
struct Edge {int nxt,to;} G[N<<1];
inline void add(int u,int v) {
	G[++tot]=(Edge){head[u],v},head[u]=tot;
	G[++tot]=(Edge){head[v],u},head[v]=tot;
}

struct Seg_Tree {
    #define mid ((l+r)>>1)
    int root[N],cnt;
    struct Tree{int l,r,d,t;} t[N*65];
    void updata(int&now,int last,int l,int r,int pos,int val) {
        now=++cnt,t[now]=t[last],t[now].d+=val,t[now].t++;
        if(l==r) return;
        if(pos<=mid) updata(t[now].l,t[last].l,l,mid,pos,val);
        else updata(t[now].r,t[last].r,mid+1,r,pos,val);
    }
	void JerryCAKIOI(int&now,int last) {t[now=++cnt]=t[last];}
    pair<int,int> query(int r1,int r2,int r3,int r4,int l,int r,int pos) {
		if(l==r) return make_pair(t[r1].t+t[r2].t-t[r3].t-t[r4].t,t[r1].d+t[r2]
		.d-t[r3].d-t[r4].d);
		if(pos<=mid) return query(t[r1].l,t[r2].l,t[r3].l,t[r4].l,l,mid,pos);
		else return query(t[r1].r,t[r2].r,t[r3].r,t[r4].r,mid+1,r,pos);
    }
	int ask(int r1,int r2,int r3,int r4) {return t[r1].d+t[r2].d-t[r3].d-t[r4].d;}
    #undef mid
}T;

int fa[N][LogN+2],dep[N];
void dfs(int u,int f) {
    if(c[u]) T.updata(T.root[u],T.root[f],1,n,c[u],d[u]);
	else T.JerryCAKIOI(T.root[u],T.root[f]);
    fa[u][0]=f,dep[u]=dep[f]+1;
    for(int i=1;i<=LogN;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=G[i].nxt) {
        int v=G[i].to;
        if(v!=f) dfs(v,u);
    }return;
}
inline int Lca(int x,int y) {
    if(x==y) return x;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LogN;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=LogN;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int main() {
	IN(n),IN(q);
	int fuck=n;
	for(int i=1;i<fuck;++i) {
		int a,b,x,y;IN(a),IN(b),IN(x),IN(y);
		++n,c[n]=x,d[n]=y,add(a,n),add(n,b);
	}
	dfs(1,0);
	for(int i=1;i<=q;++i) {
		int x,y,u,v;
		IN(x),IN(y),IN(u),IN(v);
		int lca=Lca(u,v),flca=fa[lca][0];
		int ans=T.ask(T.root[u],T.root[v],T.root[lca],T.root[flca]);
		pair<int,int> res=T.query(T.root[u],T.root[v],T.root[lca],T.root[flca],1,n,x);
		ans-=res.second,ans+=res.first*y;
		printf("%d\n",ans);
	}
    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<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=2.5e5+7;
const int LogN=35;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

int c[N],d[N],head[N],n,q,tot;
struct Edge {int nxt,to;} G[N<<1];
inline void add(int u,int v) {
	G[++tot]=(Edge){head[u],v},head[u]=tot;
	G[++tot]=(Edge){head[v],u},head[v]=tot;
}

struct Seg_Tree {
    #define mid ((l+r)>>1)
    int root[N],cnt;
    struct Tree{int l,r,d,t;} t[N*65];
    void updata(int&now,int last,int l,int r,int pos,int val) {
        now=++cnt,t[now]=t[last],t[now].d+=val,t[now].t++;
        if(l==r) return;
        if(pos<=mid) updata(t[now].l,t[last].l,l,mid,pos,val);
        else updata(t[now].r,t[last].r,mid+1,r,pos,val);
    }
	void JerryCAKIOI(int&now,int last) {t[now=++cnt]=t[last];}
    pair<int,int> query(int r1,int r2,int r3,int r4,int l,int r,int pos) {
		if(l==r) return make_pair(t[r1].t+t[r2].t-t[r3].t-t[r4].t,t[r1].d+t[r2]
		.d-t[r3].d-t[r4].d);
		if(pos<=mid) return query(t[r1].l,t[r2].l,t[r3].l,t[r4].l,l,mid,pos);
		else return query(t[r1].r,t[r2].r,t[r3].r,t[r4].r,mid+1,r,pos);
    }
	int ask(int r1,int r2,int r3,int r4) {return t[r1].d+t[r2].d-t[r3].d-t[r4].d;}
    #undef mid
}T;

int fa[N][LogN+2],dep[N];
void dfs(int u,int f) {
    if(c[u]) T.updata(T.root[u],T.root[f],1,n,c[u],d[u]);
	else T.JerryCAKIOI(T.root[u],T.root[f]);
    fa[u][0]=f,dep[u]=dep[f]+1;
    for(int i=1;i<=LogN;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=G[i].nxt) {
        int v=G[i].to;
        if(v!=f) dfs(v,u);
    }return;
}
inline int Lca(int x,int y) {
    if(x==y) return x;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LogN;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    if(x==y) return x;
    for(int i=LogN;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int main() {
	IN(n),IN(q);
	int fuck=n;
	for(int i=1;i<fuck;++i) {
		int a,b,x,y;IN(a),IN(b),IN(x),IN(y);
		++n,c[n]=x,d[n]=y,add(a,n),add(n,b);
	}
	dfs(1,0);
	for(int i=1;i<=q;++i) {
		int x,y,u,v;
		IN(x),IN(y),IN(u),IN(v);
		int lca=Lca(u,v),flca=fa[lca][0];
		int ans=T.ask(T.root[u],T.root[v],T.root[lca],T.root[flca]);
		pair<int,int> res=T.query(T.root[u],T.root[v],T.root[lca],T.root[flca],1,n,x);
		ans-=res.second,ans+=res.first*y;
		printf("%d\n",ans);
	}
    return 0;
}
```