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.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static ArrayList<Edge>[] adj;
	static ArrayList<Query>[] queries;
	static int [] ans;
	static int [] freq;
	static int [] len;
	static int tot;
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		adj = new ArrayList[n];
		for(int i=0;i<n;i++) {
			adj[i] = new ArrayList<>();
		}
		for(int i=0;i<n-1;i++) {
			int a = sc.nextInt()-1;
			int b = sc.nextInt()-1;
			int c = sc.nextInt();
			int d = sc.nextInt();
			adj[a].add(new Edge(b,c,d));
			adj[b].add(new Edge(a,c,d));
		}
		LCA lca= new LCA(adj);
		queries = new ArrayList[n];
		for(int i=0;i<n;i++) {
			queries[i] = new ArrayList<>();
		}
		ans = new int[q];
		freq = new int[n];
		len = new int[n];
		tot =0;
		for(int i=0;i<q;i++) {
			int x = sc.nextInt();
			int y=  sc.nextInt();
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			int tempLCA = lca.lca(u,v);
			queries[u].add(new Query(x,y,i,false));
			queries[v].add(new Query(x,y,i,false));
			queries[tempLCA].add(new Query(x,y,i,true));
		}
		dfs(0,0);
		StringBuilder sb=  new StringBuilder();
		for(int i=0;i<q;i++) {
			sb.append(ans[i]);
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	//maybe change dfs values to facilitate adding
	static void dfs(int curr,int par) {
		if(curr==0) {
			//continue:
		}
		else {
			int tempLen = 0;
			int tempColor = 0;
			for(Edge x : adj[curr]) {
				if(x.dest==par) {
					tempLen = x.len;
					tempColor= x.color;
				}
			}
			freq[tempColor]++;
			len[tempColor]+=tempLen;
			tot+=tempLen;
			
		}
//		System.out.println(tot);
		for(Query temp : queries[curr]) {
			int tempColor =temp.x;
			int newLen = temp.y;
			int delta = newLen*freq[tempColor]-len[tempColor]+tot;
			if(temp.par) {
				ans[temp.index]-=2*delta;
			}
			else {
				ans[temp.index]+=delta;
			}
		}
		for(Edge x : adj[curr]) {
			if(x.dest!=par) {
				dfs(x.dest,curr);
			}
		}
		int tempLen = 0;
		int tempColor = 0;
		for(Edge x : adj[curr]) {
			if(x.dest==par) {
				tempLen = x.len;
				tempColor= x.color;
			}
		}
		freq[tempColor]--;
		len[tempColor]-=tempLen;
		tot-=tempLen;
		
		
	}
	static class Edge{
		int dest;
		int color;
		int len;
		public Edge(int d,int c,int l) {
			this.dest = d;
			this.color =c;
			this.len = l;
		}
	}
	static class Query{
		int x;
		int y;
		int index;
		boolean par;
		public Query(int x,int y,int i, boolean b) {
			this.x = x;
			this. y = y;
			this.index = i;
			this.par = b;
		}
	}
	static class LCA{
		int [] parent;
		int [][] anc;
		int [] depth;
		ArrayList<Edge>[] tree;
		
		public LCA(ArrayList<Edge>[] tree) {
			this.tree=tree;
			depth = new int[tree.length];
			anc = new int[tree.length][21];
			parent = new int[tree.length];

			initializeParent();
			initializeDepth();
			initializeAnc();
		}
		/*
		 * initialize depth
		 */
		void initializeDepth() {

			depth[0] = 0;
			Queue<Integer> q = new LinkedList<Integer>();
			q.add(0);
			while(!q.isEmpty()) {
				int x = q.poll();
				for(Edge next : tree[x]) {
					if(next.dest!=parent[x]) {
						depth[next.dest] = depth[x]+1;
						q.add(next.dest);
					}
				}
			}
		}
		/*
		 * initialize parent
		 */
		void initializeParent() {
			Queue<Integer> q = new LinkedList<Integer>();
			q.add(0);
			while(!q.isEmpty()) {
				int x = q.poll();
				for(Edge next : tree[x]) {
					if(next.dest!=parent[x]) {
						parent[next.dest] = x;
						q.add(next.dest);
					}
				}
			}
		}
		/*
		 * initialize ancestor 
		 */
		void initializeAnc() {
			for(int i=0;i<tree.length;i++) {
				anc[i][0] = parent[i];
			}
			for(int j=1;j<=20;j++) {
				for(int i=0;i<tree.length;i++) {
					anc[i][j] = anc[anc[i][j-1]][j-1];
				}
			}
		}
		/*
		 * given two node numbers computes the lca node
		 */
		int lca(int x,int y) {
			if(depth[x]<depth[y]) {
				int temp = x;
				x=y;
				y=temp;
			}
			for(int i=20;i>=0;i--) {
				if(depth[x]-(int) Math.pow(2,i)>=depth[y]) {
					x=anc[x][i];
				}
			}
			if(x==y) {
				return x;
			}
			for(int i=20;i>=0;i--) {
				if(anc[x][i] !=anc[y][i]) {
					x=anc[x][i];
					y=anc[y][i];
				}
			}
			return anc[x][0];

		}
	}
}