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

public class Main{

    private static int MAX_ASCENDANTS = 20;
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int q = sc.nextInt();
        Node nodes[] = new Node[n];
        for (int i=0; i<n; i++) nodes[i] = new Node(i);
        List<ColorChange> colors[] = new List[n];
        for (int i=0; i<n; i++) colors[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();
            nodes[a].edges.add(new Edge(c, d, nodes[b]));
            nodes[b].edges.add(new Edge(c, d, nodes[a]));
        }

        dfs(nodes[0], null, 0, 0, 0, colors);

        for (int i=1; i<MAX_ASCENDANTS; i++){
            for (int j=0; j<n; j++){
                if (nodes[j].ascendants[i-1]!=null) nodes[j].ascendants[i]=nodes[nodes[j].ascendants[i-1].id].ascendants[i-1];
            }
        }
        for (int i=0; i<n; i++){
            for (int j=1; j<colors[i].size(); j++){
                ColorChange prev = colors[i].get(j-1);
                ColorChange next = colors[i].get(j);
                next.num += prev.num;
                next.dist += prev.dist;
            }
        }

        StringBuilder sb = new StringBuilder();
        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;
            Node lca = lca(nodes[u], nodes[v]);
            List<ColorChange> c = colors[x];
            sb.append(dist(nodes[u], c, y) + dist(nodes[v], c, y) - 2*dist(lca, c, y)).append('\n');
        }
        System.out.println(sb.toString());
    }


    private static long dist(Node node, List<ColorChange> changes, int newLen){
        long d = node.dist;
        ColorChange c = upperBound(changes, node.order);
        if (c!=null){
            d += (long) c.num*newLen -c.dist;
        }
        return d;
    }

    private static ColorChange upperBound(List<ColorChange> a, int k){
        int left = -1;
        int right = a.size();
        while (right-left>1){
            int mid = (left+right)/2;
            if (a.get(mid).pos<=k){
                left=mid;
            }else{
                right=mid;
            }
        }
        if (left<0)return null;
        return a.get(left);
    }

    private static Node lca(Node u, Node v){
        if (u.depth>v.depth) return lca(v,u);
        for (int i=0; i<MAX_ASCENDANTS; i++){
            int diff = v.depth-u.depth;
            if ((diff & (1<<i))!=0){
                v = v.ascendants[i];
            }
        }
        if (u==v)return u;
        for (int i=MAX_ASCENDANTS-1; i>=0; i--){
            if (u.ascendants[i]!=v.ascendants[i]){
                u=u.ascendants[i];
                v=v.ascendants[i];
            }
        }
        return u.ascendants[0];
    }

    private static int dfs(Node node, Node parent, int order, int depth, int dist, List<ColorChange>[] colors){
        node.ascendants[0] = parent;
        node.order = order;
        node.depth = depth;
        node.dist = dist;
        for (Edge e : node.edges){
            if (e.to!=parent){
                order++;
                colors[e.color].add(new ColorChange(order, 1, e.length));
                order = dfs(e.to, node, order, depth+1, dist+e.length, colors);
                colors[e.color].add(new ColorChange(order+1, -1, -e.length));
            }
        }
        return order;
    }


    private static class Edge{
        final int color;
        final int length;
        final Node to;

        private Edge(int color, int length, Node to){
            this.color = color;
            this.length = length;
            this.to = to;
        }
    }

    private static class Node{
        final int id;
        int order;
        int depth;
        int dist;
        List<Edge> edges = new ArrayList<>();
        Node ascendants[] = new Node[MAX_ASCENDANTS];

        private Node(int id){
            this.id = id;
        }
    }

    private static class ColorChange{
        final int pos;
        int dist;
        int num;

        private ColorChange(int pos, int num, int dist){
            this.pos = pos;
            this.num = num;
            this.dist = dist;
        }
    }
}