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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, Q = map(int, input().split())

path = [[] for _ in range(N)]

for _ in range(N-1) :
    a, b, c, d = (int(i) for i in input().split())
    path[a-1].append((b-1, c-1, d))
    path[b-1].append((a-1, c-1, d))

# doublingに必要なKを求める
for K in range(18) :
    if 2 ** K >= N :
        break

# dfs
parent = [[-1] * N for _ in range(K)]
rank = [-1 for _ in range(N)]

rank[0] = 0
queue = [0]

while queue :
    cur = queue.pop()
    for nex, _, _ in path[cur] :
        if rank[nex] < 0 :
            queue.append(nex)
            parent[0][nex] = cur
            rank[nex] = rank[cur] + 1

# doubling        
for i in range(1, K) :
    for j in range(N) :
        if parent[i-1][j] > 0 :
            parent[i][j] = parent[i-1][parent[i-1][j]]

# lca
def lca(a, b) :
    if rank[a] > rank[b] :
        a, b = b, a

    diff = rank[b] - rank[a]
    i = 0
    while diff > 0 :
        if diff & 1 :
            b = parent[i][b]
        diff >>= 1
        i += 1
        
    if a == b :
        return a

    for i in range(K-1, -1, -1) :
        if parent[i][a] != parent[i][b] :
            a = parent[i][a]
            b = parent[i][b]

    return parent[0][a]

# Queryの先読み
schedule = [[] for _ in range(N)]
for i in range(Q) : 
    x, y, u, v = map(int, input().split())
    x, u, v = x-1, u-1, v-1
    l = lca(u, v)
    schedule[u].append((i, 1, x, y))
    schedule[v].append((i, 1, x, y))
    schedule[l].append((i, -2, x, y))

ret = [0] * Q
C = [0] * (N-1)
D = [0] * (N-1)

def dfs(cur, pre, tot) :
    for i, t, c, d in schedule[cur] :
        ret[i] += t * (tot - D[c] + C[c] * d)
    
    for nex, c, d in path[cur] :
        if nex == pre :
            continue
        C[c] += 1
        D[c] += d
        dfs(nex, cur, tot + d)
        C[c] -= 1
        D[c] -= d

dfs(0, -1, 0)
   
for i in range(Q) :
    print(ret[i])