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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
#define M 100005
int n,q,i,x,y,h[M],nx[M<<1],r[M<<1],c[M],v[M],tot,s,d,l,si[M],son[M],top[M],dep[M],fa[M],ans[M],cc[M],cs[M];
void add(int x,int y) {
	r[++tot]=y,nx[tot]=h[x],h[x]=tot;
}
struct node {
	int x,c,d,id;
} w;
vector<node>a[M],b[M];
void dfs(int x,int f) {
	si[x]=1,fa[x]=f;
	for(int i=h[x]; i!=-1; i=nx[i])
		if(r[i]!=f) {
			for(int j=0; j<a[r[i]].size(); j++)
				if(a[r[i]][j].x==x) {
					c[r[i]]=a[r[i]][j].c,v[r[i]]=a[r[i]][j].d;
					break;
				}
			dep[r[i]]=dep[x]+v[r[i]],dfs(r[i],x),si[x]+=si[r[i]];
			if(si[r[i]]>si[son[x]])son[x]=r[i];
		}
}
void rdfs(int x,int f) {
	if(son[x])top[son[x]]=top[x],rdfs(son[x],x);
	for(int i=h[x]; i!=-1; i=nx[i])
		if(r[i]!=f&&r[i]!=son[x])top[r[i]]=r[i],rdfs(r[i],x);
}
int lca(int x,int y) {
	while(top[x]!=top[y])
		if(dep[top[x]]<dep[top[y]])y=fa[top[y]];
		else x=fa[top[x]];
	return dep[x]>dep[y]?y:x;
}
void redfs(int x,int f) {
	for(int i=0; i<b[x].size(); i++)
		ans[b[x][i].id]+=b[x][i].x*(cc[b[x][i].c]*b[x][i].d-cs[b[x][i].c]);
	for(int i=h[x]; i!=-1; i=nx[i])
		if(r[i]!=f)cc[c[r[i]]]++,cs[c[r[i]]]+=v[r[i]],redfs(r[i],x),cc[c[r[i]]]--,cs[c[r[i]]]-=v[r[i]];
}
int main() {
	scanf("%d%d",&n,&q),memset(h,-1,sizeof(h));
	for(i=1; i<n; i++)scanf("%d%d%d%d",&x,&y,&s,&d),add(x,y),add(y,x),a[x].push_back((node)<%y,s,d%>),a[y].push_back((node)<%x,s,d%>);
	dfs(1,0),rdfs(1,0);
	for(i=1; i<=q; i++)scanf("%d%d%d%d",&s,&d,&x,&y),l=lca(x,y),ans[i]=dep[x]+dep[y]-2*dep[l],w=(node)<%1,s,d,i%>,b[x].push_back(w),b[y].push_back(w),w.x=-2,b[l].push_back(w);
	redfs(1,0);
	for(i=1; i<=q; i++)printf("%d\n",ans[i]);
	return 0;
}