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;
const int M=1e5+5;

int n,m;
struct Edge{int v,to,c,d;}E[M<<1];int Head[M],e_tot;
void Link(int u,int v,int c,int d){E[++e_tot]=(Edge){v,Head[u],c,d},Head[u]=e_tot;}

int Fa[M],siz[M],son[M],tp[M],dep[M],dis[M];
void dfs_Init(int u){
	siz[u]=1;
	for(int i=Head[u];i;i=E[i].to){
		int v=E[i].v;if(v==Fa[u])continue;
		int d=E[i].d;
		dep[v]=dep[u]+1;dis[v]=dis[u]+d;Fa[v]=u;
		dfs_Init(v);
		siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void re_dfs_Init(int u){
	for(int i=Head[u];i;i=E[i].to){
		int v=E[i].v;if(v==Fa[u])continue;
		tp[v]=v==son[u]?tp[u]:v;
		re_dfs_Init(v);
	}
}
int LCA(int u,int v){
	while(tp[u]!=tp[v])
		if(dep[tp[u]]<dep[tp[v]])v=Fa[tp[v]];
		else u=Fa[tp[u]];
	return dep[u]<dep[v]?u:v;
}

int Cnt[M],Len[M];
int Ans[M];
struct qry{
	int c,y,delt,id;
};vector<qry>Q[M*3];

void dfs(int u){
	for(unsigned int qi=0;qi<Q[u].size();qi++){
		qry q=Q[u][qi];
		int ad=q.delt*(dis[u]+Cnt[q.c]*q.y-Len[q.c]);
		Ans[q.id]+=ad;
	}
	for(int i=Head[u];i;i=E[i].to){
		int v=E[i].v;if(v==Fa[u])continue;
		int c=E[i].c,d=E[i].d;
		Cnt[c]++;Len[c]+=d;
		dfs(v);
		Cnt[c]--;Len[c]-=d;
	}
}

void Solve(){
	dfs_Init(1);re_dfs_Init(1);
	for(int i=1;i<=m;i++){
		int x,y,u,v;scanf("%d%d%d%d",&x,&y,&u,&v);
		int g=LCA(u,v);
		Q[u].push_back((qry){x,y,1,i});
		Q[v].push_back((qry){x,y,1,i});
		Q[g].push_back((qry){x,y,-2,i});
	}
	dfs(1);
	for(int i=1;i<=m;i++)printf("%d\n",Ans[i]);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v,c,d;scanf("%d%d%d%d",&u,&v,&c,&d);
		Link(u,v,c,d);Link(v,u,c,d);
	}
	Solve();
	return 0;
}