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 be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

struct edge{ll to, col, len;};
struct query{ll col, id, cff, y;};
ll n;
vector<vector<edge> > v(100001);
vector<ll> ans;
vector<vector<query> > qs(100001);
ll past[100001][20];
ll dist[100001], euc[100001];


void dfs(int now, int count, ll sum = 0, int p = -1){
	past[now][0] = p;
	dist[now] = count;
	euc[now] = sum;
	for(auto& e:v[now]){
		if(e.to == p)continue;
		dfs(e.to, count+1, sum + e.len, now);
	}
	return;
}

void dinit(){
	for(int j=0;j<19;j++)for(int i=0;i<n;i++)if(past[i][j] != -1) past[i][j+1] = past[past[i][j]][j];
	return;
}

ll par(ll now, ll m){
	for(int i=0, j=1;j<=m;i++,j*=2) if(m&j) now = past[now][i];
	return now;
}

ll lca(ll a,ll b){
	if(dist[a] < dist[b]) b = par(b, dist[b] - dist[a]);
	else if(dist[a] > dist[b]) a = par(a, dist[a] - dist[b]);
	ll le = -1, ri = dist[a], mid;
	while(ri - le > 1){
		mid = (ri + le) / 2;
		if(par(a,mid) == par(b,mid)) ri = mid;
		else le = mid;
	}
	return par(a, ri);
}

ll dis(ll a, ll b){ return euc[a] + euc[b] - euc[lca(a, b)] * 2;}

ll cnt[100001];
ll sum[100001];

void dfs2(int now, int p = -1){
	for(auto q: qs[now]){
		ll x = -sum[q.col];
		x += q.y*cnt[q.col];
		ans[q.id] += x*q.cff;
	}
	for(auto& e: v[now]){
		if(e.to == p) continue;
		cnt[e.col]++; sum[e.col] += e.len;
		dfs2(e.to, now);
		cnt[e.col]--; sum[e.col] -= e.len;
	}
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    memset(past,-1,sizeof(past));
    int q;
    cin >> n >> q; ans.resize(q);
    for(int i=1;i<n;i++){
    	int a, b, c, d;
    	cin >> a >> b >> c >> d;
    	a--;b--;
    	v[a].push_back({b,c,d});
    	v[b].push_back({a,c,d});
    }
    dfs(0, 0);
    dinit();
    for(int i=0;i<q;i++){
    	ll x, y, a, b;
    	cin >> x >> y >> a >> b;
    	a--;b--;
    	qs[a].push_back({x,i,1,y});
    	qs[b].push_back({x,i,1,y});
    	qs[lca(a,b)].push_back({x,i,-2,y});
    	ans[i] = dis(a,b);
    }
    dfs2(0);
    for(auto& i:ans) cout << i << endl;
    return 0;
}