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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define LL long long
#define MAXN 200000
#define MOD 1000000007
int n,q,pre[MAXN+5],ecnt,BLK,pcnt;
int F[MAXN+5][20];
int dfn[MAXN+5],ed[MAXN+5],ct,fd[MAXN+5],dep[MAXN+5];
int col[MAXN+5],val[MAXN+5],flag[MAXN+5],ans[MAXN+5],cnt[MAXN+5];
int sum[MAXN+5];
struct edge{
	int to,nxt,col,dis;
}e[MAXN*2+5];
struct Query{
	int l,r,id,x,y;
}Q[MAXN+5];
bool cmp(Query s1,Query s2){
	if(s1.l/BLK==s2.l/BLK)return s1.r<s2.r;
	else return s1.l<s2.l;
}
void add(int u,int v,int a,int b){
	e[++ecnt]=(edge){v,pre[u],a,b};
	pre[u]=ecnt;
	e[++ecnt]=(edge){u,pre[v],a,b};
	pre[v]=ecnt;
}
void dfs(int x,int fa){
	dfn[x]=++ct,fd[ct]=x;
	F[x][0]=fa,dep[x]=dep[fa]+1;
	for(int k=1;k<20;k++)
	F[x][k]=F[F[x][k-1]][k-1];
	for(int i=pre[x];i!=-1;i=e[i].nxt){
		int xnt=e[i].to;
		if(xnt==fa)continue;
		dfs(xnt,x);
		col[xnt]=e[i].col,val[xnt]=e[i].dis;
	}
	ed[x]=++ct,fd[ct]=x;
}
int LCA(int a,int b)
{
	if(dep[b]>dep[a])swap(a,b);
	for(int i=19;i>=0;i--)
	if(dep[F[a][i]]>=dep[b])a=F[a][i];
	if(a==b)return a;
	for(int i=19;i>=0;i--)
	if(F[a][i]!=F[b][i])
	a=F[a][i],b=F[b][i];
	return F[a][0];
}
void upd(int x){
    int y=fd[x];
    if(flag[y])cnt[col[y]]--,sum[col[y]]-=val[y],pcnt-=val[y];
    else cnt[col[y]]++,sum[col[y]]+=val[y],pcnt+=val[y];
    flag[y]^=1;
}
int main(){
	scanf("%d%d",&n,&q);
	BLK=floor(sqrt(n));
	memset(pre,-1,sizeof(pre));
	for(int i=1;i<n;i++){
		int u,v,a,b;
		scanf("%d%d%d%d",&u,&v,&a,&b);
		add(u,v,a,b);
	}
	dfs(1,0);
	for(int i=1;i<=q;i++){
		int x,y,u,v;
		scanf("%d%d%d%d",&x,&y,&u,&v);
		int p=LCA(u,v);
		if(u==p||v==p){
			if(dep[v]<dep[u])swap(u,v);
			Q[i]=(Query){dfn[u]+1,dfn[v],i,x,y};
		}
		else{
			if(dfn[v]<dfn[u])swap(u,v);
			Q[i]=(Query){ed[u],dfn[v],i,x,y};
		}
	}
	sort(Q+1,Q+q+1,cmp);
	int L=1,R=0;
	for(int i=1;i<=q;i++){
		while(L<Q[i].l)upd(L++);
		while(L>Q[i].l)upd(--L);
		while(R>Q[i].r)upd(R--);
		while(R<Q[i].r)upd(++R);
		ans[Q[i].id]=pcnt-sum[Q[i].x]+cnt[Q[i].x]*Q[i].y;
	}
	for(int i=1;i<=q;i++)
	printf("%d\n",ans[i]);
}