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 <cstdio>
#include <vector>

//CONSTRAINTS
const int MN = 1e5 + 100;
const int MS = 4e6;

int N, Q;
struct node
{
public:
	int l, r;
	int c, d;
};
node seg[MS];
int X = MN;
void upd(int n, int l, int r, int ql, int qr, int xd)
{
	if(ql <= l&&r <= qr)
		++seg[n].c, seg[n].d += xd;
	else
	{
		int m=l+(r-l)/2;
		if(ql<m) upd(seg[n].l?seg[n].l:seg[n].l=X++, l, m, ql, qr, xd);
		if(m<qr) upd(seg[n].r?seg[n].r:seg[n].r=X++, m, r, ql, qr, xd);
	}
}
int C, D;
void qry(int n, int l, int r, int q)
{
	if(!n)return;
	C+=seg[n].c, D+=seg[n].d;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(q<m) qry(seg[n].l, l, m, q);
		else qry(seg[n].r, m, r, q);
	}
}

struct edg
{
public:
	int n, c, d;
};
std::vector<edg> a[MN];
int p[MN][20], d[MN], l[MN], pre[MN], post[MN], t;
void dfs(int n=1)
{
	pre[n] = t++;
	for(int i=0;p[n][i]&&p[p[n][i]][i];++i)
		p[n][i+1]=p[p[n][i]][i];
	for(auto x:a[n])
		if(x.n!=p[n][0])
		{
			d[x.n]=d[n]+1;
			l[x.n] = l[n]+x.d;
			p[x.n][0]=n;
			dfs(x.n);
			upd(x.c, 0, N, pre[x.n], post[x.n], x.d);
		}
	post[n] = t;
}
int lca(int a, int b)
{
	if(a==b)return a;
	if(d[b]<d[a])std::swap(a,b);
	for(int i=0,j=d[b]-d[a];(1<<i)<=j;++i)
		if(j>>i&1)
			b=p[b][i];
	if(a==b)return a;
	for(int i=31-__builtin_clz(d[a]);i>=0;--i)
		if(p[a][i]&&p[a][i]!=p[b][i])
			a=p[a][i],b=p[b][i];
	return p[a][0];
}
int main(void)
{
	scanf("%d%d", &N, &Q);
	for(int i = 0;i+1 < N;++i)
	{
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		::a[a].push_back({b, c, d});
		::a[b].push_back({a, c, d});
	}
	dfs();
	for(int i=0,x,y,u,v,c,d;i<Q;++i)
	{
		scanf("%d%d%d%d", &x,&y,&u,&v);
		int z = lca(u, v);

		C=D=0;
		qry(x, 0, N, pre[u]);
		qry(x, 0, N, pre[v]);
		c=C,d=D;
		C=D=0;
		qry(x, 0, N, pre[z]);
		c-=2*C,d-=2*D;
		printf("%d\n", c*y+(l[u]+l[v]-2*l[z])-d);
	}
	return 0;
}