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<queue>
#include<tuple>
#define mid ((l+r)>>1)
using namespace std;
namespace fio{
	streambuf*in=cin.rdbuf();
	char bb[1000000], *s=bb, *t=bb;
	#define gc() (s==t&&(t=(s=bb)+in->sgetn(bb,1000000),s==t)?EOF:*s++)
	inline int read(){
		int x=0;
		char ch=gc();
		while(ch<48)ch=gc();
		while(ch>=48)x=x*10+ch-48,ch=gc();
		return x;
	}
}using fio::read;
using mp=pair<int,int>;
using mt=tuple<int,int,int>;
int n, m;
vector<mt>road[100005];
int sz[3000005], ls[3000005], rs[3000005], cnt; long long sum[3000005];
int root[100005], dep[100005];
inline void add(int&root, int x, int l, int r, int p, int v){
	sz[root=++cnt]=sz[x]+1, sum[root]=sum[x]+v;
	if(l!=r)if(p<=mid)add(ls[root], ls[x], l, mid, p, v), rs[root] = rs[x];else add(rs[root], rs[x], mid + 1, r, p, v), ls[root] = ls[x];else;
}
inline long long sub(int x, int l, int r, int p, int v){
	if(!x)return 0;
	if(l==r)return 1ll * v * sz[x] - sum[x];
	return p<=mid?sub(ls[x], l, mid, p, v) : sub(rs[x], mid + 1, r, p, v);
}
int anc[100005][20];
long long ps[100005];
void dfs(int x, int p){
	anc[x][0]=p, dep[x]=dep[p]+1;for(int i=1;i<20;i++)anc[x][i]=anc[anc[x][i-1]][i-1];
	for(mt it:road[x])if(get<0>(it)!=p)ps[get<0>(it)]=ps[x]+get<2>(it), add(root[get<0>(it)], root[x], 1, n, get<1>(it), get<2>(it)), dfs(get<0>(it), x);
}
int lca(int x, int y){
	if(dep[x]<dep[y])swap(x, y);
	for(int i=19;~i;i--)if(dep[anc[x][i]]>=dep[y])x=anc[x][i];
	if(x==y)return x;
	for(int i=19;~i;i--)if(anc[x][i]!=anc[y][i])x=anc[x][i], y=anc[y][i];
	return anc[x][0];
}
int main(){
	n=read(), m=read();
	for(int i=1, x, y, c, v;i<n;i++)x=read(), y=read(), c=read(), v=read(), road[x].emplace_back(y, c, v), road[y].emplace_back(x, c, v);
	dfs(1, 0);
	for(int i=1;i<=m;i++){
		int c=read(), v=read(),x=read(), y=read(), __lca=lca(x, y);
		printf("%lld\n", ps[x] + ps[y] - (ps[__lca]<<1)
			+ sub(root[x], 1, n, c, v) + sub(root[y], 1, n, c, v) - (sub(root[__lca], 1, n, c, v)<<1));
	}
}