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>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 1000007
#define INF63 1061109567
#define INF127 9187201950435737471
#define F first
#define S second
#define ll long long
#define N 200010
using namespace std;
ll n,dp[N],f[N][32],ans[N],num[N],wei[N];
vector<pair<ll,pair<ll,ll> > > vt[N];
vector<pair<pair<ll,ll>,pair<ll,ll> > > ds[N];
void dfs(ll x,ll lst,ll d)
{
	ll i;
	dp[x]=d;
	for(i=0;i<30;i++)
	{
		f[x][i+1]=f[f[x][i]][i];
	}
	for(i=0;i<vt[x].size();i++)
	{
		if(vt[x][i].F!=lst)
		{
			f[vt[x][i].F][0]=x;
			dfs(vt[x][i].F,x,d+1);
		}
	}
	return;
}
ll glca(ll x,ll y)
{
	ll i;
	if(dp[x]<dp[y])
	{
		swap(x,y);
	}
	for(i=30;i>=0;i--)
	{
		if(dp[f[x][i]]>=dp[y])
		{
			x=f[x][i];
		}
		if(x==y)
		{
			return x;
		}
	}
    for(i=30;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
void dfs2(ll x,ll lst,ll sow)
{
	ll i,y;
	pair<pair<ll,ll>,pair<ll,ll> > p;
	pair<ll,pair<ll,ll> > p2;
	for(i=0;i<ds[x].size();i++)
	{
		p=ds[x][i];
		if(p.S.S==0)
		{
			ans[p.S.F]+=sow*p.F.S;
		}
		else if(p.S.S==1)
		{
			ans[p.S.F]+=wei[p.F.F]*p.F.S;
		}
		else
		{
			ans[p.S.F]+=num[p.F.F]*p.F.S;
		}
	}
	for(i=0;i<vt[x].size();i++)
	{
		p2=vt[x][i];
		if(p2.F==lst)
		{
			continue;
		}
		num[p2.S.F]++;
		wei[p2.S.F]+=p2.S.S;
		dfs2(p2.F,x,sow+p2.S.S);
		wei[p2.S.F]-=p2.S.S;
		num[p2.S.F]--;
	}
	return;
}
int main(){
	ll i,x,y,q,col,w,a;
	scanf("%lld%lld",&n,&q);
	for(i=1;i<n;i++)
	{
		scanf("%lld%lld%lld%lld",&x,&y,&col,&w);
		x--;
		y--;
		vt[x].push_back(make_pair(y,make_pair(col,w)));
		vt[y].push_back(make_pair(x,make_pair(col,w)));
	}
	dfs(0,-1,0);
	for(i=0;i<q;i++)
	{
		scanf("%lld%lld%lld%lld",&col,&w,&x,&y);
		x--;
		y--;
		a=glca(x,y);
		ds[x].push_back(make_pair(make_pair(0,1),make_pair(i,0)));
		ds[x].push_back(make_pair(make_pair(col,-1),make_pair(i,1)));
		ds[x].push_back(make_pair(make_pair(col,w),make_pair(i,2)));
		ds[y].push_back(make_pair(make_pair(0,1),make_pair(i,0)));
		ds[y].push_back(make_pair(make_pair(col,-1),make_pair(i,1)));
		ds[y].push_back(make_pair(make_pair(col,w),make_pair(i,2)));
		ds[a].push_back(make_pair(make_pair(0,-2),make_pair(i,0)));
		ds[a].push_back(make_pair(make_pair(col,2),make_pair(i,1)));
		ds[a].push_back(make_pair(make_pair(col,-w*2),make_pair(i,2)));
	}
	dfs2(0,-1,0);
	for(i=0;i<q;i++)
	{
		printf("%lld\n",ans[i]);
	}
	return 0;
}