#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
typedef pair<int, int> pii;
struct segtree{
	struct node{
		int cnt, sum;
		node *ch[2];
	}pl[20*MAXN + 5], *NIL, *ncnt;
	segtree(){NIL = ncnt = &pl[0]; NIL->ch[0] = NIL->ch[1] = NIL;}
	node *add(node *pre, int l, int r, int pos, int del) {
		node *nw = (++ncnt); (*nw) = (*pre);
		if( l == r ) {
			nw->cnt++, nw->sum += del;
			return nw;
		}
		int mid = (l + r) >> 1;
		if( pos <= mid ) nw->ch[0] = add(pre->ch[0], l, mid, pos, del);
		else nw->ch[1] = add(pre->ch[1], mid + 1, r, pos, del);
		return nw;
	}
	pii query(node *nw, int l, int r, int pos) {
		if( l == r )
			return make_pair(nw->cnt, nw->sum);
		int mid = (l + r) >> 1;
		if( pos <= mid ) return query(nw->ch[0], l, mid, pos);
		else return query(nw->ch[1], mid + 1, r, pos);
	}
}T;
segtree::node *rt[MAXN + 5];
struct edge{
	int dis, clr, to;
	edge *nxt;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];
void addedge(int u, int v, int c, int d) {
	edge *p = (++ecnt);
	p->to = v, p->clr = c, p->dis = d;
	p->nxt = adj[u], adj[u] = p;
	p = (++ecnt);
	p->to = u, p->clr = c, p->dis = d;
	p->nxt = adj[v], adj[v] = p;
}
int N, Q;
int fa[20][MAXN + 5], dep[MAXN + 5];
int dis[MAXN + 5];
void dfs(int x, int f) {
	fa[0][x] = f;
	for(int i=1;i<20;i++)
		fa[i][x] = fa[i-1][fa[i-1][x]];
	dep[x] = dep[f] + 1;
	for(edge *p=adj[x];p;p=p->nxt) {
		if( p->to == f ) continue;
		rt[p->to] = T.add(rt[x], 1, N-1, p->clr, p->dis);
		dis[p->to] = dis[x] + p->dis;
		dfs(p->to, x);
	}
}
int lca(int u, int v) {
	if( dep[u] < dep[v] ) swap(u, v);
	for(int i=19;i>=0;i--)
		if( dep[fa[i][u]] >= dep[v] )
			u = fa[i][u];
	if( u == v ) return u;
	for(int i=19;i>=0;i--)
		if( fa[i][u] != fa[i][v] )
			u = fa[i][u], v = fa[i][v];
	return fa[0][u];
}
int main() {
	scanf("%d%d", &N, &Q);
	for(int i=1;i<N;i++) {
		int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
		addedge(a, b, c, d);
	}
	rt[1] = T.NIL, dfs(1, 0);
	for(int i=1;i<=Q;i++) {
		int x, y, u, v; scanf("%d%d%d%d", &x, &y, &u, &v);
		int p = lca(u, v);
		pii a = T.query(rt[u], 1, N-1, x), b = T.query(rt[v], 1, N-1, x), c = T.query(rt[p], 1, N-1, x);
		printf("%d\n", (dis[u]+dis[v]-2*dis[p]) - (a.second+b.second-2*c.second) + (a.first+b.first-2*c.first)*y);
	}
}
### Prompt

Please formulate a CPP solution to the following 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

### Response

```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
typedef pair<int, int> pii;
struct segtree{
	struct node{
		int cnt, sum;
		node *ch[2];
	}pl[20*MAXN + 5], *NIL, *ncnt;
	segtree(){NIL = ncnt = &pl[0]; NIL->ch[0] = NIL->ch[1] = NIL;}
	node *add(node *pre, int l, int r, int pos, int del) {
		node *nw = (++ncnt); (*nw) = (*pre);
		if( l == r ) {
			nw->cnt++, nw->sum += del;
			return nw;
		}
		int mid = (l + r) >> 1;
		if( pos <= mid ) nw->ch[0] = add(pre->ch[0], l, mid, pos, del);
		else nw->ch[1] = add(pre->ch[1], mid + 1, r, pos, del);
		return nw;
	}
	pii query(node *nw, int l, int r, int pos) {
		if( l == r )
			return make_pair(nw->cnt, nw->sum);
		int mid = (l + r) >> 1;
		if( pos <= mid ) return query(nw->ch[0], l, mid, pos);
		else return query(nw->ch[1], mid + 1, r, pos);
	}
}T;
segtree::node *rt[MAXN + 5];
struct edge{
	int dis, clr, to;
	edge *nxt;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0];
void addedge(int u, int v, int c, int d) {
	edge *p = (++ecnt);
	p->to = v, p->clr = c, p->dis = d;
	p->nxt = adj[u], adj[u] = p;
	p = (++ecnt);
	p->to = u, p->clr = c, p->dis = d;
	p->nxt = adj[v], adj[v] = p;
}
int N, Q;
int fa[20][MAXN + 5], dep[MAXN + 5];
int dis[MAXN + 5];
void dfs(int x, int f) {
	fa[0][x] = f;
	for(int i=1;i<20;i++)
		fa[i][x] = fa[i-1][fa[i-1][x]];
	dep[x] = dep[f] + 1;
	for(edge *p=adj[x];p;p=p->nxt) {
		if( p->to == f ) continue;
		rt[p->to] = T.add(rt[x], 1, N-1, p->clr, p->dis);
		dis[p->to] = dis[x] + p->dis;
		dfs(p->to, x);
	}
}
int lca(int u, int v) {
	if( dep[u] < dep[v] ) swap(u, v);
	for(int i=19;i>=0;i--)
		if( dep[fa[i][u]] >= dep[v] )
			u = fa[i][u];
	if( u == v ) return u;
	for(int i=19;i>=0;i--)
		if( fa[i][u] != fa[i][v] )
			u = fa[i][u], v = fa[i][v];
	return fa[0][u];
}
int main() {
	scanf("%d%d", &N, &Q);
	for(int i=1;i<N;i++) {
		int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
		addedge(a, b, c, d);
	}
	rt[1] = T.NIL, dfs(1, 0);
	for(int i=1;i<=Q;i++) {
		int x, y, u, v; scanf("%d%d%d%d", &x, &y, &u, &v);
		int p = lca(u, v);
		pii a = T.query(rt[u], 1, N-1, x), b = T.query(rt[v], 1, N-1, x), c = T.query(rt[p], 1, N-1, x);
		printf("%d\n", (dis[u]+dis[v]-2*dis[p]) - (a.second+b.second-2*c.second) + (a.first+b.first-2*c.first)*y);
	}
}
```