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;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

pair<pair<int,int>, pair<int, int>> E[200001];
int H[100001];
int P[100001][20];
int D[100001], RD[100001];

int oya(int A, int B) {
	if (B == 0) return A;
	int k = 31 - __builtin_clz(B);
	return oya(P[A][k], B - (1 << k));
}
void dfs(int A, int B, int C, int d) {
	RD[A] = B;
	D[A] = d;
	P[A][0] = C;
	int mae = C;
	rep(i, 19) {
		P[A][i + 1] = P[mae][i];
		mae = P[A][i + 1];
	}
	for (int i = H[A]; i; i = E[i].first.second) {
		if (E[i].first.first != C) dfs(E[i].first.first, B + E[i].second.first, A, d + 1);
	}
}

pair<int, int> QE[300001];
int QH[100001];
int CD[100001], CN[100001];
void dfs2(int A, int C) {
	int tmp;
	for (int i = QH[A]; i; i = tmp) {
		tmp = QE[i].second;
		QE[i].second = CN[QE[i].first];
		QE[i].first = CD[QE[i].first];
	}
	for (int i = H[A]; i; i = E[i].first.second) {
		if (E[i].first.first != C) {
			CD[E[i].second.second] += E[i].second.first;
			CN[E[i].second.second]++;
			dfs2(E[i].first.first, A);
			CD[E[i].second.second] -= E[i].second.first;
			CN[E[i].second.second]--;
		}
	}
}


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	
	int N, Q;
	cin >> N >> Q;
	for (int i = 1; i < N + N - 1; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		E[i] = mp(mp(b, H[a]), mp(d, c));
		H[a] = i++;
		E[i] = mp(mp(a, H[b]), mp(d, c));
		H[b] = i;
	}

	dfs(1, 0, 0, 0);

	int motoD[100000], y[100000];
	rep(i, Q) {
		int x, u, v;
		cin >> x >> y[i] >> u >> v;

		if (D[u] > D[v]) swap(u, v);
		int sa = D[v] - D[u];

		int L = 0;
		int R = D[u];
		while (L < R) {
			int half = (L + R) / 2;
			if (oya(u, half) == oya(v, sa + half)) R = half;
			else L = half + 1;
		}
		int o = oya(u, L);
		motoD[i] = RD[u] + RD[v] - RD[o] * 2;
		QE[i * 3 + 1] = mp(x, QH[u]);
		QH[u] = i * 3 + 1;
		QE[i * 3 + 2] = mp(x, QH[v]);
		QH[v] = i * 3 + 2;
		QE[i * 3 + 3] = mp(x, QH[o]);
		QH[o] = i * 3 + 3;
	}

	dfs2(1, 0);

	rep(i, Q) {
		motoD[i] -= QE[i * 3 + 1].first + QE[i * 3 + 2].first - 2 * QE[i * 3 + 3].first;
		motoD[i] += (QE[i * 3 + 1].second + QE[i * 3 + 2].second - 2 * QE[i * 3 + 3].second) * y[i];
		co(motoD[i]);
	}

	Would you please return 0;
}