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 JAVA):

Solution:

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	class Edge{
		int to;
		int color;
		int cost;
		public Edge(int to, int color, int cost) {
			this.to=to;
			this.color=color;
			this.cost=cost;
		}
	}

	ArrayList<ArrayList<Edge>> es = new ArrayList<>();
	class Lca{
		int l;
		int n;
		int parent[][];
		int dist[];
		int cost[];
		public Lca() {
			n = es.size();
			l = 0;
			while((1<<l) < n) {
				l++;
			}
			parent = new int[n][l];
			dist = new int[n];
			cost = new int[n];
		}
		public void dfs(int r, int p, int di, int co) {
			if(p != -1) {
				parent[r][0] = p;
			}
			dist[r] = di;
			cost[r] = co;
			for(Edge e : es.get(r)) {
				if(e.to == p) continue;
				dfs(e.to, r, di+1, co + e.cost);
			}
		}
		public void init() {
			dfs(0, -1, 0, 0);
			for(int i=0; i<l-1; i++) {
				for(int v = 0; v<n; v++) {
					parent[v][i+1] = parent[parent[v][i]][i];
				}
			}
		}
		public int get(int a, int b) {
			if(dist[a]>dist[b]) {
				int tmp = a;
				a = b;
				b = tmp;
			}
			int gap = dist[b]-dist[a];
			for(int i=l-1; i>=0; i--) {
				int len = 1<<i;
				if(gap>=len) {
					gap -= len;
					b = parent[b][i];
				}
			}
			if(a==b) return a;
			for(int i=l-1; i>=0; i--) {
				int na = parent[a][i];
				int nb = parent[b][i];
				if(na != nb) {
					a = na;
					b = nb;
				}
			}
			return parent[a][0];
		}
		public int dist(int a, int b) {
			int c = get(a,b);
			return dist[a] + dist[b] - 2 * dist[c];
		}
		public int cost(int a, int b) {
			int c = get(a,b);
			return cost[a] + cost[b] - 2 * cost[c];
		}
	}

	class Query{
		int color;
		int qid;
		int y;
		int coeff;

		Query(int color, int qid, int coeff, int y){
			this.color=color;
			this.qid=qid;
			this.coeff=coeff;
			this.y=y;
		}
	}

	ArrayList<ArrayList<Query>> qs = new ArrayList<>();
	long ans[];
	int sum[];
	int cnt[];
	public void dfs2(int r, int p) {
		for(Query q : qs.get(r)) {
			long x = 0;
			x -= sum[q.color];
			x += (long)q.y*cnt[q.color];
			ans[q.qid] += x * q.coeff;
		}
		for(Edge e : es.get(r)) {
			if(e.to == p) continue;
			cnt[e.color]++;
			sum[e.color]+=e.cost;
			dfs2(e.to, r);
			cnt[e.color]--;
			sum[e.color]-=e.cost;
		}
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		sum = new int[n];
		cnt = new int[n];
		for(int i=0; i<n; i++) {
			es.add(new ArrayList<>());
		}
		for(int i=0; i<n-1; i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			a--; b--;
			int color = sc.nextInt();
			int cost = sc.nextInt();
			es.get(a).add(new Edge(b, color, cost));
			es.get(b).add(new Edge(a, color, cost));
		}
		Lca lca = new Lca();
		lca.init();

		ans = new long[q];
		for(int i=0; i<n; i++) {
			qs.add(new ArrayList<>());
		}


		for(int i=0; i<q; i++) {
			int col = sc.nextInt();
			int y = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			a--; b--;
			int c = lca.get(a,b);
			ans[i] = lca.cost(a, b);
			qs.get(a).add(new Query(col, i, 1, y));
			qs.get(b).add(new Query(col, i, 1, y));
			qs.get(c).add(new Query(col, i, -2, y));
		}

		dfs2(0,-1);

		for(int i=0; i<q; i++) {
			System.out.println(ans[i]);
		}
		sc.close();
	}
}