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 <iostream>
#include <vector>
#include <utility>
#include <map>

using namespace std;
const int LOG = 22;
vector<pair<int,int>> G[100010];
vector<pair<int,pair<int,int>>> H[100010];
int parent[25][100010];
int d[100010],dist[100010];
void dfs(int v, int p){
	for(auto x:G[v]){
		if(x.first==p) continue;
		parent[0][x.first] = v;
		d[x.first] = d[v] + 1;
		dist[x.first] = dist[v] + x.second;
		dfs(x.first,v);
	}
}

void init(int v,int root){
	d[root] = 0; parent[0][root] = -1;
	dfs(root,-1);
	for(int k=0;k+1<LOG;k++){
		for(int i=0;i<v;i++){
			if(parent[k][i]<0){
				parent[k+1][i] = -1;
			}else{
				parent[k+1][i] = parent[k][parent[k][i]];
			}
		}
	}
}

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

int c[100010] = {},cdist[100010] = {};
vector<int> v[100010];
map<pair<int,int>,pair<int,int>> mp;
void dfs2(int s,int p){
	for(int x:v[s]){
		mp[{s,x}] = {c[x],cdist[x]};
	}
	for(auto x:H[s]){
		if(x.first==p) continue;
		pair<int,int> q = x.second;
		c[q.first]++; cdist[q.first] += q.second;
		dfs2(x.first,s);
		c[q.first]--; cdist[q.first] -= q.second;
	}
}

int solve(int v,int c,int num){
	return dist[v] - mp[{v,c}].second + mp[{v,c}].first*num;
}

int x[100010],y[100010],s[100010],t[100010];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int i,n,q;
	cin >> n >> q;
	for(i=0;i<n-1;i++){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		a--; b--;
		G[a].push_back({b,d}); G[b].push_back({a,d});
		H[a].push_back({b,{c,d}}); H[b].push_back({a,{c,d}});
	}
	init(n,0);
	for(i=0;i<q;i++){
		cin >> x[i] >> y[i] >> s[i] >> t[i];
		s[i]--; t[i]--;
		v[s[i]].push_back(x[i]); v[t[i]].push_back(x[i]); v[lca(s[i],t[i])].push_back(x[i]);
	}
	dfs2(0,-1);
	for(i=0;i<q;i++){
		cout << solve(s[i],x[i],y[i]) + solve(t[i],x[i],y[i]) - 2*solve(lca(s[i],t[i]),x[i],y[i]) << "\n";
	}
}