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;
const int N = 2e5 + 10 , Lg = 25;
int timer;
int fix[N] , sum[N] , sums[N] , in[N] , out[N] , color[N] , edge[N] , u[N] , v[N] , l[N] , col_u[N] , col_v[N] , col_l[N] , sum_u[N] , sum_v[N] , sum_l[N] , res[N] , L[N][Lg];
vector < pair < pair < int , int > , int > > query[N];
vector < pair < int , pair < int , int > > > edges[N];
inline bool upper(int a , int b){
	return (!a || (in[a] <= in[b] && out[a] >= out[b])) ? 1 : 0;
}
inline void dfs(int x , int p , int c , int d){
	fix[c] ++;
	sums[c] += d;
	for(int i = 0; i < query[x].size(); i ++){
		int color = query[x][i].first.second;
		int id = query[x][i].first.first;
		int ty = query[x][i].second;
		if(ty == 1) col_u[id] = fix[color] , sum_u[id] = sums[color]; 
		if(ty == 2) col_v[id] = fix[color] , sum_v[id] = sums[color];
		if(ty == 3) col_l[id] = fix[color] , sum_l[id] = sums[color]; 
	}
	for(int i = 0; i < edges[x].size(); i ++){
		int u = edges[x][i].first;
		int cx = edges[x][i].second.first;
		int dx = edges[x][i].second.second;
		if(u != p)
			dfs(u , x , cx , dx);
	}
	fix[c] --;
	sums[c] -= d;
}
inline void rec(int x , int p , int c , int d){
	sum[x] = sum[p] + d;
	in[x] = ++timer;
	L[x][0] = p;
	for(int i = 1; i < Lg; i ++)
		L[x][i] = L[L[x][i - 1]][i - 1];
	for(int i = 0; i < edges[x].size(); i ++){
		int u = edges[x][i].first;
		int cx = edges[x][i].second.first;
		int dx = edges[x][i].second.second;
		if(u != p)
			rec(u , x , cx , dx);
	}
	out[x] = ++timer;  
}
inline int lca(int a , int b){
	if(upper(a , b)) return a;
	if(upper(b , a)) return b;
	for(int i = Lg - 1; i >= 0; i --)
		if(!upper(L[a][i] , b)) a = L[a][i];
	return L[a][0]; 
}
int main(){
	int n , q;
	cin >> n >> q;
	for(int i = 1; i < n; i ++){
		int a , b , c , d;
		scanf("%d%d%d%d" , &a , &b , &c , &d); 
		edges[a].push_back({b , {c , d}});
		edges[b].push_back({a , {c , d}});
	}
	rec(1 , 0 , 0 , 0);
	for(int i = 1; i <= q; i ++){
		scanf("%d%d%d%d" , &color[i] , &edge[i] , &u[i] , &v[i]);
		l[i] = lca(v[i] , u[i]);
		query[u[i]].push_back({{i , color[i]} , 1});
		query[v[i]].push_back({{i , color[i]} , 2});
		query[l[i]].push_back({{i , color[i]} , 3});
	}
	dfs(1 , 0 , 0 , 0);
	for(int i = 1; i <= q; i ++){
		int fr = u[i] , to = v[i] , lc = l[i] , c = color[i] , ed = edge[i];
		int dist = sum[fr] + sum[to] - 2 * sum[lc];
		int num_col = col_u[i] + col_v[i] - 2 * col_l[i];
		int dist_col = sum_u[i] + sum_v[i] - 2 * sum_l[i]; 
		res[i] = dist - dist_col + num_col * ed;
	}
	for(int i = 1; i <= q; i ++) printf("%d\n" , res[i]);
}