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;
long long a,b,c,d,e,tes,t,i,j,jm[100009],raod[100009],n,msh[100009][19],lc,tim,lf[100009],rg[100009],dep[100009],x,y;
pair <long long, long long> mas[100009][3];
vector <pair <long long, pair <long long, long long> > > v[100009];
pair <pair <long long, long long>, pair <long long, long long> > p[100009];
vector <pair <long long, pair <long long, long long> > > g[100009];
void dfsst(long long q, long long w){
	tim++;
	lf[q]=rg[q]=tim;
	msh[q][0]=w;
	for(i=1; i<=18; i++) msh[q][i]=msh[msh[q][i-1]][i-1];
	for(vector <pair <long long, pair <long long, long long> > >::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		dep[(*it).first]=dep[q]+(*it).second.second;
		dfsst((*it).first,q);
		if(rg[q]<rg[(*it).first]) rg[q]=rg[(*it).first];
	}
}
bool anc(long long q, long long w){
	if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
long long lca(long long q, long long w){
	if(anc(q,w)) return q;
	if(anc(w,q)) return w;
	for(long long h=18; h>=0; h--){
		if(msh[q][h]!=0&&anc(msh[q][h],w)==0) q=msh[q][h];
	}
	return msh[q][0];
}
void dfs(long long q, long long w){
	for(long long h=0; h<g[q].size(); h++){
		mas[g[q][h].second.first][g[q][h].second.second].first=raod[g[q][h].first];
		mas[g[q][h].second.first][g[q][h].second.second].second=jm[g[q][h].first];
	}
	for(vector <pair <long long, pair <long long, long long> > >::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		jm[(*it).second.first]+=(*it).second.second;
		raod[(*it).second.first]++;
		dfs((*it).first,q);
		jm[(*it).second.first]-=(*it).second.second;
		raod[(*it).second.first]--;
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>tes;
	for(i=1; i<n; i++){
		cin>>a>>b>>c>>d;
		v[a].push_back(make_pair(b,make_pair(c,d)));
		v[b].push_back(make_pair(a,make_pair(c,d)));
	}
	dfsst(1,0);
	for(t=1; t<=tes; t++){
		cin>>p[t].first.first>>p[t].first.second>>p[t].second.first>>p[t].second.second;
		lc=lca(p[t].second.first,p[t].second.second);
		g[lc].push_back(make_pair(p[t].first.first,make_pair(t,2)));
		g[p[t].second.first].push_back(make_pair(p[t].first.first,make_pair(t,1)));
		g[p[t].second.second].push_back(make_pair(p[t].first.first,make_pair(t,0)));
	}
	dfs(1,0);
	for(t=1; t<=tes; t++){
		c=mas[t][0].first+mas[t][1].first-mas[t][2].first*2;
		d=mas[t][0].second+mas[t][1].second-mas[t][2].second*2;
      y=p[t].first.second;
		cout<<dep[p[t].second.first]+dep[p[t].second.second]-dep[lca(p[t].second.first,p[t].second.second)]*2-d+y*c<<endl;
	}
	return 0;
}