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 <map>
using namespace std;

struct edge{
    int to,col,dist;
};

class LCA{
private:
	vector<vector<edge>> v;
	vector<vector<int>> parent;
	vector<int> depth;
	void dfs(int n,int m,int d){
		parent[0][n] = m;
		depth[n] = d;
		for(auto x:v[n]){
			if(x.to!=m) dfs(x.to,n,d+1);
		}
	}
public:
	LCA(int N,int root,vector<vector<edge>>& tree){
		v = tree;
		parent = vector<vector<int>>(21,vector<int>(N+1,0));
		depth = vector<int>(N+1,0);
		dfs(root,-1,0);
		for(int j=0;j+1<20;j++){
			for(int i=1;i<=N;i++){
				if(parent[j][i]<0) parent[j+1][i] = -1;
				else parent[j+1][i] = parent[j][parent[j][i]];
			}
		}
	}
	int lca(int n,int m){
		if(depth[n]>depth[m]) swap(n,m);
		for(int j=0;j<20;j++){
			if((depth[m]-depth[n]) >> j&1) m = parent[j][m];
		}
		if(n==m) return n;
		for(int j=19;j>=0;j--){
			if(parent[j][n]!=parent[j][m]){
				n = parent[j][n];
				m = parent[j][m];
			}
		}
		return parent[0][n];
	}
	int dep(int n){return depth[n];}
};

struct query{
    int col,value,id;
    bool is_lca;
};

struct color{
    int dist,num;
};

void dfs(int now,int par,int d,vector<vector<query>>& q,vector<vector<edge>>&tree,vector<int>& ans,map<int,color>& m){
    for(auto x:q[now]){
        int res;
        if(!m.count(x.col)) res = d;
        else res = d-m[x.col].dist+x.value*m[x.col].num;
        if(x.is_lca) ans[x.id] -= 2*res;
        else ans[x.id] += res;
    }
    for(auto x:tree[now]) if(x.to!=par){
        m[x.col].dist += x.dist;
        m[x.col].num++;
        dfs(x.to,now,d+x.dist,q,tree,ans,m);
        m[x.col].dist -= x.dist;
        m[x.col].num--;
    }
}
    

int main(){
    int N,Q;
    cin >> N >> Q;
    vector<vector<edge>> tree(N+1);
    for(int i=0;i<N-1;i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        tree[a].push_back({b,c,d});
        tree[b].push_back({a,c,d});
    }
    LCA lca(N,1,tree);
    vector<vector<query>> q(N+1);
    vector<int> ans(Q,0);
    for(int i=0;i<Q;i++){
        int x,y,u,v;
        cin >> x >> y >> u >> v;
        q[u].push_back({x,y,i,false});
        q[v].push_back({x,y,i,false});
        q[lca.lca(u,v)].push_back({x,y,i,true});
    }
    map<int,color> m;
    dfs(1,0,0,q,tree,ans,m);
    for(auto x:ans) cout << x << endl;
}