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

Solution:
def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.buffer.readline
    int_ = int

    # クエリは0-indexedで[l, r)
    class SparseTable():
        def __init__(self, A):
            # A: 処理したい数列
            self.N = len(A)
            self.K = self.N.bit_length() - 1
            self.table = [[0] * (self.K + 1) for _ in range(self.N)]
            for i, a in enumerate(A):
                self.table[i][0] = a
            for k in range(1, self.K + 1):
                for i in range(self.N):
                    j = i + (1 << (k - 1))
                    if j <= self.N - 1:
                        self.table[i][k] = STfunc(self.table[i][k - 1], self.table[j][k - 1])
                    else:
                        self.table[i][k] = self.table[i][k - 1]

        def query(self, l, r):
            # [l, r)の最小値を求める
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l][k], self.table[r - (1 << k)][k])

    # adj[0] must be empty list
    def EulerTour(adj, root):
        st = [root]
        ret = []
        seen = [0] * len(adj)
        par = [0] * len(adj)
        depth = [0] * len(adj)
        while st:
            v = st.pop()
            if seen[v]:
                ret.append(v)
                continue
            ret.append(v)
            seen[v] = 1
            if par[v] != 0:
                st.append(par[v])
            for u in adj[v]:
                if seen[u] == 0:
                    st.append(u)
                    par[u] = v
                    depth[u] = depth[v] + 1

        return ret, depth

    N, Q = map(int_, input().split())
    adj = [[] for _ in range(N + 1)]
    E = {}
    for _ in range(N - 1):
        a, b, c, d = map(int_, input().split())
        adj[a].append(b)
        adj[b].append(a)
        E[a * (N + 1) + b] = (c, d)
        E[b * (N + 1) + a] = (c, d)

    et, depth = EulerTour(adj, 1)
    left = [-1] * (N + 1)
    right = [-1] * (N + 1)
    dist_from_root = [-1] * (N + 1)
    dist_from_root[1] = 0
    color_info = [[] for _ in range(N)]
    color_d = [[] for _ in range(N)]
    for i, v in enumerate(et):
        if left[v] < 0:
            left[v] = i
        right[v] = i
        if i != 0:
            u = et[i - 1]
            c, d = E[v * (N + 1) + u]
            if dist_from_root[v] < 0:
                dist_from_root[v] = dist_from_root[u] + d
            if depth[u] < depth[v]:
                color_info[c].append(i)
                if not color_d[c]:
                    color_d[c].append((1, d))
                else:
                    prev_num, prev_d = color_d[c][-1]
                    color_d[c].append((prev_num + 1, prev_d + d))
            else:
                color_info[c].append(i)
                prev_num, prev_d = color_d[c][-1]
                color_d[c].append((prev_num - 1, prev_d - d))

    # min
    def STfunc(a, b):
        if depth[a] < depth[b]:
            return a
        else:
            return b

    ST = SparseTable(et)
    for _ in range(Q):
        x, y, u, v = map(int_, input().split())
        lca = ST.query(min(left[u], left[v]), max(right[u], right[v]) + 1)
        if color_info[x]:
            le = len(color_info[x])
            iu = bisect_left(color_info[x], left[u] + 1) - 1
            if iu == -1:
                du = dist_from_root[u]
            else:
                num_u, dist_u = color_d[x][iu]
                du = dist_from_root[u] + num_u * y - dist_u

            iv = bisect_left(color_info[x], left[v] + 1) - 1
            if iv == -1:
                dv = dist_from_root[v]
            else:
                num_v, dist_v = color_d[x][iv]
                dv = dist_from_root[v] + num_v * y - dist_v

            ilca = bisect_left(color_info[x], left[lca] + 1) - 1
            if ilca == -1:
                dlca = dist_from_root[lca]
            else:
                num_lca, dist_lca = color_d[x][ilca]
                dlca = dist_from_root[lca] + num_lca * y - dist_lca

            print(du + dv - 2 * dlca)
        else:
            print(dist_from_root[u] + dist_from_root[v] - 2 * dist_from_root[lca])


if __name__ == '__main__':
    main()