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

public class Main {
  private static int MAX_GEN_ASCENDANTS = 20;
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int N = scanner.nextInt();
    int Q = scanner.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 = scanner.nextInt() - 1;
      int b = scanner.nextInt() - 1;
      int c = scanner.nextInt();
      int d = scanner.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_GEN_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 = scanner.nextInt();
      int y = scanner.nextInt();
      int u = scanner.nextInt() - 1;
      int v = scanner.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.print(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_GEN_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_GEN_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 Node {
    final int id;
    int order;
    int depth;
    int dist;
    List<Edge> edges = new ArrayList<>();
    Node[] ascendants = new Node[MAX_GEN_ASCENDANTS];

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

  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 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;
    }
  }
}