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 Maxn=100003;
int par[17][Maxn],root,depth[Maxn],n,T,dist[Maxn];
vector<int>G[Maxn];
vector<pair<int,int> >v[Maxn];
void dfs(int x,int p,int d){
	par[0][x]=p;
	depth[x]=d;
	for(int i=0;i<G[x].size();i++)
		if(G[x][i]!=p)
			dfs(G[x][i],x,d+1);
}
void init(){
	dfs(root,-1,0);
	for(int k=0;k<16;k++)
		for(int x=0;x<n;x++)
			if(par[k][x]<0)
				par[k+1][x]=-1;
			else
				par[k+1][x]=par[k][par[k][x]];
}
int lca(int x,int y){
	if(depth[x]>depth[y])swap(x,y);
	for(int k=0;k<17;k++)
		if((depth[y]-depth[x])>>k&1)
			y=par[k][y];
	if(x==y)return x;
	for(int k=16;k>-1;k--)
		if(par[k][x]!=par[k][y])
			x=par[k][x],
			y=par[k][y];
	return par[0][x];
} 
void DFS(int x,int dis,int p){
	dist[x]=dis;
	for(int i=0;i<G[x].size();i++)
		if(p!=G[x][i])
			DFS(G[x][i],dis+v[x][i].second,x);
}
int cnt[Maxn],sum[Maxn],ans[Maxn];
vector<pair<int,pair<int,int> > >add[Maxn],era[Maxn];
void Findans(int x,int p){
	for(int i=0;i<add[x].size();i++){
		int pos=add[x][i].first,c=add[x][i].second.first,val=add[x][i].second.second;
		ans[pos]+=dist[x];ans[pos]-=sum[c];ans[pos]+=cnt[c]*val; 
	}
	for(int i=0;i<era[x].size();i++){
		int pos=era[x][i].first,c=era[x][i].second.first,val=era[x][i].second.second;
		ans[pos]-=2*dist[x];ans[pos]+=2*sum[c];ans[pos]-=2*cnt[c]*val; 
	}
	for(int i=0;i<G[x].size();i++)
		if(G[x][i]!=p)
		{
			cnt[v[x][i].first]++;
			sum[v[x][i].first]+=v[x][i].second; 
			Findans(G[x][i],x);
			cnt[v[x][i].first]--;
			sum[v[x][i].first]-=v[x][i].second; 
		}
}
int main(){
	scanf("%d%d",&n,&T);
	for(int i=1;i<n;i++){
		int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
		a--;b--;c--;G[a].push_back(b),v[a].push_back(make_pair(c,d));
		G[b].push_back(a),v[b].push_back(make_pair(c,d));
	} 
	DFS(0,0,-1);init();
	for(int i=0;i<T;i++){
		int x,y,u,v;
		scanf("%d%d%d%d",&x,&y,&u,&v);
		x--;u--;v--;
		int w=lca(u,v);
		add[u].push_back(make_pair(i,make_pair(x,y)));
		add[v].push_back(make_pair(i,make_pair(x,y)));
		if(w!=-1)era[w].push_back(make_pair(i,make_pair(x,y)));
	}
	Findans(0,-1);
	for(int i=0;i<T;i++)cout<<ans[i]<<'\n'; 
}