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;

const int mod = 1e9 + 7, N = 1e5 + 10;

ll pw(ll a, ll b)
{
	ll r = 1;
	for(; b ; b >>= 1, a = a * a % mod)
	{
		if(b & 1)
		{
			r = r * a % mod;
		}
	}
	return r;
}

ll getinv(ll n)
{
	return pw(n, mod - 2);
}

void upd(ll &a, ll b)
{
	a = (a + b) % mod;
}

int n, q;

ll cnt[N]; // 记录每个颜色出现次数
ll sum[N]; // 记录每个颜色的边权和
ll S;

struct E
{
	int v, c, w;
};
vector<E> g[N];

int fa[N][22], dep[N];

struct T
{
	int ids;
	int x, y; // 把颜色x的长度都改成y
	int tag; // 对答案贡献 +-1
};
vector<T> G[N];
ll ans[N];

int main()
{
	scanf("%d%d", &n, &q);
	for(int i = 1 ; i < n ; ++ i)
	{
		int u, v, c, w;
		scanf("%d%d%d%d", &u, &v, &c, &w);
		g[u].push_back((E)
		{
			v, c, w
		});
		g[v].push_back((E)
		{
			u, c, w
		});
	}
	if(1)
	{
		function<void(int, int)> dfs = [&](int u, int fa)
		{
			dep[u] = dep[fa] + 1;
			:: fa[u][0] = fa;
			for(int i = 1 ; i <= 20 ; ++ i)
			{
				:: fa[u][i] = :: fa[:: fa[u][i - 1]][i - 1];
			}
			for(auto e : g[u])
			{
				int v = e.v;
				if(v != fa)
				{
					dfs(v, u);
				}
			}
		};
		dfs(1, 0);
	}

	function<int(int, int)> getlca = [&](int u, int v)
	{
		if(dep[u] < dep[v])
		{
			swap(u, v);
		}
		for(int i = 20 ; ~ i ; -- i)
		{
			if(dep[fa[u][i]] >= dep[v])
			{
				u = fa[u][i];
			}
		}
		if(u == v)
		{
			return u;
		}
		for(int i = 20 ; ~ i ; -- i)
		{
			if(fa[u][i] != fa[v][i])
			{
				u = fa[u][i];
				v = fa[v][i];
			}
		}
		return fa[u][0];
	};

	for(int i = 1 ; i <= q ; ++ i)
	{
		int x, y, u, v;
		scanf("%d%d%d%d", &x, &y, &u, &v);
		int lca = getlca(u, v);
		G[u].push_back((T)
		{
			i, x, y, 1
		});
		G[v].push_back((T)
		{
			i, x, y, 1
		});
		G[lca].push_back((T)
		{
			i, x, y, -2
		});
	}

	if(1)
	{
		function<void(int, int)> dfs = [&](int u, int fa)
		{
			for(auto e : G[u])
			{
				ll val = S - sum[e.x] + (ll) cnt[e.x] * e.y;
				ans[e.ids] += val * e.tag;
			}
			for(auto e : g[u])
			{
				int v = e.v;
				if(v != fa)
				{
					++ cnt[e.c];
					sum[e.c] += e.w;
					S += e.w;
					dfs(v, u);
					-- cnt[e.c];
					sum[e.c] -= e.w;
					S -= e.w;
				}
			}
		};
		dfs(1, 0);
	}

	for(int i = 1 ; i <= q ; ++ i)
	{
		printf("%lld\n", ans[i]);
	}
}