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 maxn 100005
struct Edge{
	int next,to,col,w;
}edge[maxn*2];
struct Tree{
	int l,r,num,sum;
}a[maxn*30];
int fi[maxn],se,n,q,depth[maxn],fa[maxn][18],si,rt[maxn],f[maxn][18];
inline void add_edge(int u,int v,int col,int w){
	edge[++se].next=fi[u],edge[se].to=v,fi[u]=se,edge[se].col=col,edge[se].w=w,
	edge[++se].next=fi[v],edge[se].to=u,fi[v]=se,edge[se].col=col,edge[se].w=w;
}
void change(int &x,int l,int r,int L,int w){
	a[++si]=a[x],x=si,a[x].num++,a[x].sum+=w;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(L<=mid)change(a[x].l,l,mid,L,w);
	else change(a[x].r,mid+1,r,L,w);
}
void dfs(int x){
	depth[x]=depth[fa[x][0]]+1;
	for(int i=1;;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
		f[x][i]=f[x][i-1]+f[fa[x][i-1]][i-1];
		if(!fa[x][i])break;
	}
	for(int i=fi[x];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa[x][0])continue;
		rt[v]=rt[x];change(rt[v],1,n,edge[i].col,edge[i].w);
		fa[v][0]=x,f[v][0]=edge[i].w;dfs(v);
	}
}
int up(int u,int k){
	for(int i=0;k;i++){
		if(k&(1<<i))k^=(1<<i),u=fa[u][i];
	}
	return u;
}
int lca(int u,int v){
	if(depth[u]>depth[v])swap(u,v);
	v=up(v,depth[v]-depth[u]);
	for(int i=17;~i;i--){
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	}
	return u==v?u:fa[u][0];
}
int dis(int u,int v){
	int k=depth[v]-depth[u],ans=0;
	for(int i=0;i<18;i++){
		if(k&(1<<i))ans+=f[v][i],v=fa[v][i];
	}
	return ans;
}
int query_num(int x1,int x2,int l,int r,int L){
	if(l==r)return a[x2].num-a[x1].num;
	int mid=(l+r)>>1;
	if(L<=mid)return query_num(a[x1].l,a[x2].l,l,mid,L);
	else return query_num(a[x1].r,a[x2].r,mid+1,r,L);
}
int query_sum(int x1,int x2,int l,int r,int L){
	if(l==r)return a[x2].sum-a[x1].sum;
	int mid=(l+r)>>1;
	if(L<=mid)return query_sum(a[x1].l,a[x2].l,l,mid,L);
	else return query_sum(a[x1].r,a[x2].r,mid+1,r,L);
}
int main(){
	int u,v,col,w;scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++)scanf("%d%d%d%d",&u,&v,&col,&w),add_edge(u,v,col,w);
	dfs(1);
	for(int i=0;i<q;i++){
		scanf("%d%d%d%d",&col,&w,&u,&v);
		int L=lca(u,v);
		int ans=dis(L,u)+dis(L,v)+(query_num(rt[L],rt[u],1,n,col)+query_num(rt[L],rt[v],1,n,col))*w-query_sum(rt[L],rt[u],1,n,col)-query_sum(rt[L],rt[v],1,n,col);
		printf("%d\n",ans);
	}
	return 0;
}