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;
#define N 100005
#define Ln 20
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define repp(i,n) for((i)=n-1;(i)>=0;(i)--)
#define F first
#define S second

int n,q;
int co[N],w[N];
int p[Ln][N];
vector<pii> e[N];
int d[N],D[N];
map<int,pii> mem[N];
int num[N],dist[N];

struct ABC133F{};
struct Tourist{};
struct Rng_58{};
struct RadeWoosh
{
	int c,len,u,v,uv;
}R[N];
void dfs(int u)
{
	int i;
	rep(i,e[u].size())
	{
		int v=e[u][i].F;
		if(v==p[0][u]) continue;
		p[0][v]=u;
		d[v]=d[u]+1;
		D[v]=D[u]+w[e[u][i].S];
		dfs(v);
	}
}
int lca(int u,int v)
{
	int i;
	if(d[u]>d[v]) swap(u,v);
	repp(i,Ln)
		if(1<<i<=d[v]-d[u]) v=p[i][v];
	repp(i,Ln)
		if(p[i][u]!=p[i][v]) u=p[i][u],v=p[i][v];
	if(u==v) return u;
	return p[0][u];
}
void dfs2(int u)
{
	int i;
	for(map<int,pii>::iterator it=mem[u].begin();it!=mem[u].end();it++)
		it->S=mp(num[it->F],dist[it->F]);
	rep(i,e[u].size())
	{
		if(e[u][i].F==p[0][u]) continue;
		int v=e[u][i].S;
		num[co[v]]++;
		dist[co[v]]+=w[v];
		dfs2(e[u][i].first);
		num[co[v]]--;
		dist[co[v]]-=w[v];
	}
}

int main()
{
	
	int i,j,Tc;
	scanf("%d%d",&n,&q);
	rep(i,n-1)
	{
		int u,v;
		scanf("%d%d%d%d",&u,&v,&co[i],&w[i]);
		e[u].pb(mp(v,i));
		e[v].pb(mp(u,i));
	}
	dfs(1);
	rep(i,Ln)
	rep(j,N)
		if(i) p[i][j]=p[i-1][p[i-1][j]];
	
	rep(Tc,q)
	{
		int c,len,u,v,uv;
		scanf("%d%d%d%d",&c,&len,&u,&v);
		uv=lca(u,v);
		pii emp=mp(0,0);
		mem[u][c]=emp;
		mem[v][c]=emp;
		mem[uv][c]=emp;
		R[Tc].c=c; R[Tc].len=len;
		R[Tc].u=u; R[Tc].v=v; R[Tc].uv=uv;
	}
	dfs2(1);
	rep(Tc,q)
	{
		int c,len,u,v,uv;
		c=R[Tc].c; len=R[Tc].len;
		u=R[Tc].u; v=R[Tc].v; uv=R[Tc].uv;
		int A=D[u]+D[v]-2*D[uv];
		int B=mem[u][c].F+mem[v][c].F-2*mem[uv][c].F;
		int C=mem[u][c].S+mem[v][c].S-2*mem[uv][c].S;
		printf("%d\n",A+len*B-C);
	}
	
	return 0;
}