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;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,Q;
vector<pair<int,int>> E[202020];
int A[101010],B[101010],C[101010],D[101010];
map<int,pair<int,ll>> memo[101010];
int num[101010];
ll dist[101010];
ll TD[101010];

int X[101010],Y[101010],U[101010],V[101010];
int P[21][200005],DD[200005];

void dfs(int cur) {
	ITR(it,E[cur]) if(it->first!=P[0][cur]) {
		TD[it->first]=TD[cur]+D[it->second];
		DD[it->first]=DD[cur]+1, P[0][it->first]=cur, dfs(it->first);
	}
}
int getpar(int cur,int up) {
	int i;
	FOR(i,20) if(up&(1<<i)) cur=P[i][cur];
	return cur;
}

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(DD[aa]>DD[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(DD[bb]-DD[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void dfs2(int cur,int pre) {
	FORR(m,memo[cur]) {
		m.second={num[m.first],dist[m.first]};
	}
	FORR(e,E[cur]) if(e.first!=pre) {
		int v=e.second;
		num[C[v]]++;
		dist[C[v]]+=D[v];
		dfs2(e.first,cur);
		num[C[v]]--;
		dist[C[v]]-=D[v];
		
	}
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		A[i]--;
		B[i]--;
		E[A[i]].push_back({B[i],i});
		E[B[i]].push_back({A[i],i});
	}
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	FOR(i,Q) {
		cin>>X[i]>>Y[i]>>U[i]>>V[i];
		U[i]--;
		V[i]--;
		memo[U[i]][X[i]]={0,0};
		memo[V[i]][X[i]]={0,0};
		x=lca(U[i],V[i]);
		memo[x][X[i]]={0,0};
	}
	dfs2(0,-1);
	FOR(i,Q) {
		x=lca(U[i],V[i]);
		ll cd=(TD[U[i]]-memo[U[i]][X[i]].second)+(TD[V[i]]-memo[V[i]][X[i]].second)-2*(TD[x]-memo[x][X[i]].second);
		int tnum=memo[U[i]][X[i]].first+memo[V[i]][X[i]].first-2*memo[x][X[i]].first;
		cout<<cd+1LL*tnum*Y[i]<<endl;
	}
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}