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 <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

#define pb push_back 

const int mo = 1e9 + 7;
const int N = 1e5 + 5;

struct Edge {
	int v, w, c;
};
int n, q;
vector<Edge> G[N];

int f[N][21], d[N], de[N], logn, id;
int T[N], L[N << 5], R[N << 5], s[N << 5], sz[N << 5];

void build(int &rt, int l, int r) {
    rt = ++ id;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    build(L[rt], l, mid);
    build(R[rt], mid + 1, r);
}

void update(int pre, int &rt, int l, int r, int x, int y) {
    rt = ++ id; sz[rt] = sz[pre] + 1; s[rt] = s[pre] + y;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(x <= mid) R[rt] = R[pre], update(L[pre], L[rt], l, mid, x, y);
    else L[rt] = L[pre], update(R[pre], R[rt], mid + 1, r, x, y);
}

void dfs(int u, int _f, int c, int w) {
	update(T[_f], T[u], 1, n, c, w);
    d[u] = d[f[u][0] = _f] + 1;
    for(int i = 1; i <= logn; i ++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for(int i = 0; i < G[u].size(); i ++) {
        int v = G[u][i].v;
        if(v != _f) {
        	de[v] = de[u] + G[u][i].w;
			dfs(v, u, G[u][i].c, G[u][i].w);
		}
    }
}

int num, sum;
void query(int f, int u, int v, int l, int r, int x) {
	if(!f || !u || !v) return ;
	if(l == r) {
		num = sz[u] + sz[v] - 2 * sz[f];
		sum = s[u] + s[v] - 2 * s[f];
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) query(L[f], L[u], L[v], l, mid, x);
	else query(R[f], R[u], R[v], mid + 1, r, x);
}

int lca(int u, int v) {
    if(d[u] < d[v]) swap(u, v);
    int c = d[u] - d[v];
    for(int i = logn; ~ i; i --)
        if(c >> i & 1) u = f[u][i];
    if(u == v) return u;
    for(int i = logn; ~ i; i --) if(f[u][i] ^ f[v][i]) 
        u = f[u][i], v = f[v][i];
    return f[u][0];
}

int main() {
	scanf("%d%d", &n, &q);
    for(logn = 1; (1 << logn) <= n; ++ logn) ;
	for(int i = 1; i < n; i ++) {
		int u, v, w, c;
		scanf("%d%d%d%d", &u, &v, &c, &w);
		G[u].pb((Edge) {v, w, c});
		G[v].pb((Edge) {u, w, c});
	}
	build(T[0], 1, n);
	dfs(1, 0, 1, 0);
	while(q --) {
		int c, w, u, v, k;
		scanf("%d%d%d%d", &c, &w, &u, &v);
		k = lca(u, v);
		num = sum = 0; query(T[k], T[u], T[v], 1, n, c);
		int dis = de[u] + de[v] - 2 * de[k];
		printf("%lld\n", dis - sum + num * 1ll * w); 
	} 
	return 0;
}