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;
struct node {
	int y,c,d;
};
vector<node>T[100001],Q[100001];
int H[100001],F[100001][18],D[100001],C[100001],CD[100001],An[100001];
void dfs(int x,int la,int d) {
	H[x]=H[la]+1,D[x]=d,F[x][0]=la;
	for(int i=0; i<T[x].size(); i++) {
		node nw=T[x][i];
		if(nw.y!=la)dfs(nw.y,x,d+nw.d);
	}
}
void dfs1(int x,int la){
	for(int i=0;i<Q[x].size();i++){
		node nw=Q[x][i];
		if(nw.y>0)An[nw.y]+=D[x]+C[nw.c]*nw.d-CD[nw.c];
		else An[-nw.y]-=2*(D[x]+C[nw.c]*nw.d-CD[nw.c]);
	}
	for(int i=0;i<T[x].size();i++){
		node nw=T[x][i];
		if(nw.y!=la)C[nw.c]++,CD[nw.c]+=nw.d,dfs1(nw.y,x),C[nw.c]--,CD[nw.c]-=nw.d;
	}
}
int LCA(int x,int y) {
	if(H[x]>H[y])swap(x,y);
	int s=H[y]-H[x];
	for(int i=0; i<=17; i++)if(s&(1<<i))y=F[y][i];
	if(x==y)return x;
	for(int i=17; i>=0; i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
	return F[x][0];
}
int main() {
	int a,b,i,j,x,y,c,d;
	cin>>a>>b;
	for(i=1; i<a; i++)scanf("%d%d%d%d",&x,&y,&c,&d),T[x].push_back({y,c,d}),T[y].push_back({x,c,d});
	dfs(1,0,0);
	for(i=1; i<=17; i++)for(j=1; j<=a; j++)F[j][i]=F[F[j][i-1]][i-1];
	for(i=1; i<=b; i++)scanf("%d%d%d%d",&c,&d,&x,&y),Q[x].push_back({i,c,d}),Q[y].push_back({i,c,d}),Q[LCA(x,y)].push_back({-i,c,d});
	dfs1(1,0);
	for(i=1;i<=b;i++)printf("%d\n",An[i]);
}