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<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<ctime>
#include<bitset>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
	int f=1,x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return f*x;
}
#define MAXN 100000
#define INF 0x3f3f3f3f
#define Mod 998244353
struct edge{int v,c,d;};
vector<edge> G[MAXN+5];
inline void Addedge(int u,int v,int c,int d){
	G[u].push_back((edge){v,c,d});
	G[v].push_back((edge){u,c,d});
	return ;
}
int n,fa[MAXN+5][20];
int dep[MAXN+5],dis[MAXN+5][20];
void DFS1(int u){
	dep[u]=dep[fa[u][0]]+1;
	for(int i=0;i<int(G[u].size());i++){
		int v=G[u][i].v;
		if(v==fa[u][0]) continue;
		fa[v][0]=u,dis[v][0]=G[u][i].d;
		DFS1(v);
	}
	return ;
}
void Prepare(){
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1],dis[i][j]=dis[i][j-1]+dis[fa[i][j-1]][j-1];
	return ;
}
pair<int,int> LCA(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	LL D=dep[u]-dep[v],d=0;
	for(int j=0;(1<<j)<=D;j++)
		if((1<<j)&D)
			d+=dis[u][j],u=fa[u][j];
	if(u==v)
		return make_pair(u,d);
	for(int j=int(log2(n));j>=0;j--)
		if(fa[u][j]!=fa[v][j]){
			d+=dis[u][j],u=fa[u][j];
			d+=dis[v][j],v=fa[v][j];
		}
	return make_pair(fa[u][0],d+dis[u][0]+dis[v][0]);
}
int ans[MAXN+5];
struct node{int id,f,col,d;};
vector<node> Q[MAXN+5];
int cnt1[MAXN+5],cnt2[MAXN+5];
void DFS(int u){//颜色数,颜色长度数
	for(int i=0;i<int(Q[u].size());i++){
		node q=Q[u][i];
		ans[q.id]=ans[q.id]-q.f*cnt2[q.col]+q.f*cnt1[q.col]*q.d;
	}
	for(int i=0;i<int(G[u].size());i++){
		edge e=G[u][i];
		if(e.v==fa[u][0]) continue;
		cnt1[e.c]++,cnt2[e.c]+=e.d;
		DFS(e.v);
		cnt1[e.c]--,cnt2[e.c]-=e.d;
	}
	return ;
}
int main(){
	n=read();int q=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read(),c=read(),d=read();
		Addedge(u,v,c,d);
	}
	DFS1(1);
	Prepare();
	for(int t=1;t<=q;t++){
		int x=read(),y=read(),u=read(),v=read();
		pair<int,int> L=LCA(u,v);
		ans[t]=L.second;
		Q[u].push_back((node){t,1,x,y});
		Q[v].push_back((node){t,1,x,y});
		Q[L.first].push_back((node){t,-2,x,y});
	}
	DFS(1);
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;
}