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 IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define endl '\n'

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 8, M = 400;

vector<pair<int, pi>> G[N];
int d[N], p[20][N], pc[N], pd[N], n, q, dis[N];
unordered_map<int, int> s[N], ct[N];
bool yes[N];

void dfs(int u = 1, int pa = 1, int dp = 0, int c = -1, int pdp = 0) {
	d[u] = dp;
	p[0][u] = pa;
	pc[u] = c;
	pd[u] = pdp;
	dis[u] = dis[pa] + pdp;
	for(auto &e:G[u])
		if(e.F != pa)
			dfs(e.F, u, dp + 1, e.S.F, e.S.S);
	if(dp % M == 0) {
		int t = u;
		while(p[0][t] != t && !yes[t]) {
			s[pc[t]][u] += pd[t];
			ct[pc[t]][u] ++;
			t = p[0][t];
		}
		if(yes[t])
			for(int i=1;i<=n-1;i++)
				s[i][u] += s[i][t], ct[i][u] += ct[i][t];
		yes[u] = true;
	}
}

int lca(int x, int y) {
	if(d[x] < d[y]) swap(x, y);
	for(int i=19;i>=0;--i)
		if(d[p[i][x]] >= d[y])
			x = p[i][x];
	if(x == y) return x;
	for(int i=19;i>=0;--i) {
		if(p[i][x] != p[i][y]) {
			x = p[i][x];
			y = p[i][y];
		}
	}
	return p[0][x];
}

pi qry(int u, int x) {
	pi ret = {0, 0};
	while(p[0][u] != u && !yes[u]) {
		ret.F += (pc[u] == x) * pd[u];
		ret.S += (pc[u] == x);
		u = p[0][u];
	}
	if(yes[u]) ret.F += s[x][u], ret.S += ct[x][u];
	return ret;
}

int qry(int u, int x, int y) {
	int ret = dis[u];
	pi pp = qry(u, x);
	ret -= pp.F;
	ret += pp.S * y;
	return ret;
}

int main()
{
	IO_OP;
	cin >> n >> q;
	for(int i=0;i<n-1;i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		G[a].PB({b, {c, d}});
		G[b].PB({a, {c, d}});
	}
	dfs();
	for(int i=1;i<20;++i) {
		for(int j=1;j<=n;++j)
			p[i][j] = p[i-1][p[i-1][j]];
	}
	while(q--) {
		int x, y, u, v;
		cin >> x >> y >> u >> v;
		cout << qry(u, x, y) + qry(v, x, y) - 2 * qry(lca(u, v), x, y) << endl;
	}
}