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 mod 998244353
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int maxn=1e5+10;
const int B=333;
vector<pii> g[maxn];
int n,q;
struct Edge
{
	int a,b,c,d;
	Edge(){}
	Edge(int a,int b,int c,int d):a(a),b(b),c(c),d(d){}
}es[maxn];
int bg[maxn],ed[maxn],DFN,dep[maxn],pa[maxn],fae[maxn],dist[maxn];
vector<int> tsum,tcnt,recsum[maxn],reccnt[maxn];
vector<pii> euler;
void dfs(int x,int fa)
{
	pa[x]=fa;
	dep[x]=dep[fa]+1;
	bg[x]=DFN++;
	if(dep[x]%B==0)
	{
		recsum[x]=tsum;
		reccnt[x]=tcnt;
	}
	euler.push_back(make_pair(dep[x],x));
	for(int i=0;i<g[x].size();i++)
	{
		int to=g[x][i].first;
		if(to==fa)continue;
		fae[to]=g[x][i].second;
		dist[to]=dist[x]+es[g[x][i].second].d;
		tsum[es[g[x][i].second].c]+=es[g[x][i].second].d;
		tcnt[es[g[x][i].second].c]++;
		dfs(to,x);
		tcnt[es[g[x][i].second].c]--;
		tsum[es[g[x][i].second].c]-=es[g[x][i].second].d;
		euler.push_back(make_pair(dep[x],x));
		DFN++;
	}
	ed[x]=DFN;
}
pii st[20][maxn*2];
int lg2[maxn*2];
inline pii rmq(int l,int r)
{
	if(l>r)swap(l,r);
	int len=lg2[r-l];
	return min(st[len][l],st[len][r-(1<<len)]);
}
struct query
{
	int x,y,u,v;
	query(){}
	query(int x,int y,int u,int v):x(x),y(y),u(u),v(v){}
};
vector<query> qs[maxn];
vector<Edge> ces[maxn];
int getans(int x,int qrc,int qry)
{
	int res=0;
	while(dep[x]%B!=0)
	{
		if(pa[x]==0)return res;
		if(es[fae[x]].c==qrc)res+=qry;
		else res+=es[fae[x]].d;
		x=pa[x];
	}
	if(x==0)return res;
	res+=dist[x];
	res-=recsum[x][qrc];
	res+=reccnt[x][qrc]*qry;
	return res;
}
int main()
{
	lg2[1]=0;
	for(int i=2;i<maxn*2;i++)lg2[i]=lg2[i>>1]+1;
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d%d",&es[i].a,&es[i].b,&es[i].c,&es[i].d);
		g[es[i].a].push_back(make_pair(es[i].b,i));
		g[es[i].b].push_back(make_pair(es[i].a,i));
		ces[es[i].c].push_back(es[i]);
	}
	tsum.resize(n);
	tcnt.resize(n);
	dfs(1,0);
	int m=euler.size();
	for(int i=0;i<m;i++)st[0][i]=euler[i];
	for(int k=1;k<20;k++)
	{
		for(int i=0;i+(1<<k)<=m;i++)
		{
			st[k][i]=min(st[k-1][i],st[k-1][i+(1<<(k-1))]);
		}
	}
	for(int i=0;i<q;i++)
	{
		int x,y,u,v;
		scanf("%d%d%d%d",&x,&y,&u,&v);
		int lca=rmq(bg[u],bg[v]).second;
		int ans=getans(u,x,y)+getans(v,x,y)-2*getans(lca,x,y);
		printf("%d\n",ans);
	}
	return 0;
}