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<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fir first
#define sec second
#define Mp make_pair
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int LB = 20 + 5;

struct Edge
{
	int next,to,c,w;
}e[MAXN<<1];
int head[MAXN],etot=0;
inline void add(int u,int v,int c,int w)
{
	e[++etot]=(Edge){ head[u],v,c,w};
	head[u]=etot;
}

int lb[MAXN];
int dep[MAXN],fa[MAXN][LB];
void lca_init(int u,int pre)
{
	for(int i=1; i<=lb[dep[u]]; ++i)
		fa[u][i] = fa[fa[u][i-1]][i-1];
	for(int i=head[u]; i; i=e[i].next)
	{
		int v=e[i].to;
		if(v==pre) continue;
		dep[v]=dep[u]+1; fa[v][0]=u;
		lca_init(v,u);
	}
}

int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=lb[dep[u]]; dep[u]>dep[v]; --i)
		if(dep[fa[u][i]] >= dep[v])
			u=fa[u][i];
	if(u==v) return u;
	for(int i=lb[dep[u]]; fa[u][0]!=fa[v][0]; --i)
		if(fa[u][i] != fa[v][i])
			u=fa[u][i],
			v=fa[v][i];
	return fa[u][0];
}

struct Query
{
	int x,y,u,v;
	ll ans;
}q[MAXM];

vector<pii> id[MAXN];

ll sum[MAXN];
int cnt[MAXN];
void dfs(int u,int pre,ll dis)
{
	for(int i=0; i<(int)id[u].size(); ++i)
	{
		Query &now = q[id[u][i].fir];
		int k = id[u][i].sec;
		
		int x = now.x;
		ll y = now.y;
		now.ans += (dis - sum[x] + cnt[x]*y) * k;
	}
	
	for(int i=head[u]; i; i=e[i].next)
	{
		int v=e[i].to, c=e[i].c, w=e[i].w;
		if(v==pre) continue;
		
		sum[c]+=w; ++cnt[c];
		dfs(v,u,dis+w);
		sum[c]-=w; --cnt[c];
	}
}

int main(void)
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1; i<n; ++i)
	{
		int u,v,c,w;
		scanf("%d%d%d%d",&u,&v,&c,&w);
		add(u,v,c,w);
		add(v,u,c,w);
	}
	
	for(int i=2; i<=n; ++i) lb[i]=lb[i>>1]+1;
	dep[0]=-1;
	lca_init(1,0);
	
	for(int i=1; i<=m; ++i)
	{
		int x,y,u,v;
		scanf("%d%d%d%d",&x,&y,&u,&v);
		q[i]=(Query){x,y,u,v,0};
		
		id[u].push_back(Mp(i,1));
		id[v].push_back(Mp(i,1));
		id[lca(u,v)].push_back(Mp(i,-2));
	}
	
	dfs(1,0,0);
	
	for(int i=1; i<=m; ++i)
		printf("%lld\n",q[i].ans);
	return 0;
}