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 rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

int n;
struct edge{
	int to, color, weight;
};
edge make_edge(int t, int c, int w){
	edge ret;
	ret.color = c;
	ret.to = t;
	ret.weight = w;
	return ret;
}
vector<edge> v[100100];
int ans[100100];
int Q;
struct query{
	int qcolor, co1, co2, pos;
};
int sum[100100], num[100100], dist;
int dep[100100], par[100100][22];
vector<query> q[100100];

void dfs1(int now){
	rep(i, 20) par[now][i+1] = par[par[now][i]][i];
	rep(i, v[now].size()){
		if(v[now][i].to != par[now][0]){
			dep[v[now][i].to] = dep[now]+1;
			par[v[now][i].to][0] = now;
			dfs1(v[now][i].to);
		}
	}
}
int lca(int a, int b){
	if(dep[a] > dep[b]) swap(a, b);
	for(int i = 20; i >= 0; i--) if(dep[par[b][i]] >= dep[a]) b = par[b][i];
	for(int i = 20; i >= 0; i--) if(par[b][i] != par[a][i]) a = par[a][i], b = par[b][i];
	if(a != b) return par[a][0];
	else return a;
}

void dfs2(int now){
	rep(i, q[now].size()){
		ans[q[now][i].pos] += q[now][i].co1 * (dist - sum[q[now][i].qcolor] + q[now][i].co2 * num[q[now][i].qcolor]);
	}
	rep(i, v[now].size()){
		if(v[now][i].to == par[now][0]) continue;
		sum[v[now][i].color] += v[now][i].weight; dist += v[now][i].weight;
		num[v[now][i].color]++;
		dfs2(v[now][i].to);
		sum[v[now][i].color] -= v[now][i].weight; dist -= v[now][i].weight;
		num[v[now][i].color]--;
	}
} 

int main(){
	scanf("%d%d", &n, &Q);
	rep(i, n-1){
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--, b--;
		v[a].push_back(make_edge(b, c, d));
		v[b].push_back(make_edge(a, c, d));
	}
	dfs1(0);
	rep(i, Q){
		int tcolor, tweight, pos1, pos2;
		scanf("%d%d%d%d", &tcolor, &tweight, &pos1, &pos2);
		pos1--, pos2--;
		int l = lca(pos1, pos2);
		query ql, q1;
		ql.co1 = -2, ql.co2 = tweight, ql.pos = i, ql.qcolor = tcolor;
		q1.co1 = +1, q1.co2 = tweight, q1.pos = i, q1.qcolor = tcolor;
		q[l].push_back(ql);
		q[pos1].push_back(q1);
		q[pos2].push_back(q1);
	}
	dfs2(0);
	rep(i, Q) cout << ans[i] << endl;
	return 0;
}