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;

vector<vector<tuple<int, int, int>>> G;

int Nl2;
vector<vector<int>> parent;
vector<int> depth;
vector<int> dist;
vector<int> num_now;
vector<int> sum_now;
map<int, int> num[100000];
map<int, int> sum[100000];
vector<vector<int>> color;

void dfs( int v, int p, int d )
{
	parent[0][v] = p;
	depth[v] = d;
	for( int i = 0; i < G[v].size(); i++ ) {
		int a, c, dd;
		tie( a, c, dd ) = G[v][i];
		if( a != p ) dfs( a, v, d + 1 );
	}
}

int lca( int u, int v )
{
	if( depth[u] > depth[v] ) swap( u, v );
	for( int k = 0; k < Nl2; k++ ) {
		if( (depth[v] - depth[u]) >> k & 1 ) {
			v = parent[k][v];
		}
	}
	if( u == v ) return u;
	for( int k = Nl2 - 1; k >= 0; k-- ) {
		if( parent[k][u] != parent[k][v] ) {
			u = parent[k][u];
			v = parent[k][v];
		}
	}
	return parent[0][u];
}

void dfs2( int v, int p )
{
	for( int c : color[v] ) {
		num[v][c] = num_now[c];
		sum[v][c] = sum_now[c];
	}
	for( auto e : G[v] ) {
		int a, c, d;
		tie( a, c, d ) = e;
		if( a == p ) continue;
		dist[a] = dist[v] + d;
		num_now[c]++;
		sum_now[c] += d;
		dfs2( a, v );
		num_now[c]--;
		sum_now[c] -= d;
	}
}

int main()
{
	int N, Q;
	cin >> N >> Q;
	G = vector<vector<tuple<int, int, int>>>( N );
	for( int i = 0; i < N - 1; i++ ) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--;
		b--;
		c--;
		G[a].push_back( make_tuple( b, c, d ) );
		G[b].push_back( make_tuple( a, c, d ) );
	}

	Nl2 = 30;
	parent = vector<vector<int>>( Nl2, vector<int>( N ) );
	depth = vector<int>( N );
	dfs( 0, -1, 0 );
	for( int k = 0; k + 1 < Nl2; k++ ) {
		for( int v = 0; v < N; v++ ) {
			if( parent[k][v] < 0 ) parent[k + 1][v] = -1;
			else parent[k + 1][v] = parent[k][ parent[k][v] ];
		}
	}

	int X[100000], Y[100000], U[100000], V[100000], A[100000];
	color = vector<vector<int>>( N );
	for( int i = 0; i < Q; i++ ) {
		cin >> X[i] >> Y[i] >> U[i] >> V[i];
		X[i]--;
		U[i]--;
		V[i]--;
		A[i] = lca( U[i], V[i] );
		color[ U[i] ].push_back( X[i] );
		color[ V[i] ].push_back( X[i] );
		color[ A[i] ].push_back( X[i] );
	}
	dist = vector<int>( N );
	num_now = vector<int>( N );
	sum_now = vector<int>( N );
	dfs2( 0, -1 );
	for( int i = 0; i < Q; i++ ) {
		int x = X[i], y = Y[i], u = U[i], v = V[i], a = A[i];
		int du = dist[u] - sum[u][x] + num[u][x] * y;
		int dv = dist[v] - sum[v][x] + num[v][x] * y;
		int da = dist[a] - sum[a][x] + num[a][x] * y;
		int ans = du + dv - da * 2;
		cout << ans << endl;
	}
}