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:
# https://atcoder.jp/contests/abc133/submissions/6316420
# 参考にさせていただきました。

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

n, q = map(int, input().split())
edges = [[] for i in range(n)]
for i in range(n-1):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    c -= 1
    edges[a].append((b,c,d))
    edges[b].append((a,c,d))

# ここで前処理
# LCAができるようにしておく
dep=[0]*n
par=[[-1]*n for i in range(18)]
# ついでに距離も持っておく
dis=[0]*n

# parent, now_point, depth, dist

def dfs(p,v,d,dd):
    dep[v]=d
    par[0][v]=p
    dis[v]=dd
    for w, _, dist in edges[v]:
        if w!=p:
            dfs(v,w,d+1, dd+dist)

def lca(a,b):
    if dep[a]>dep[b]:
        a,b=b,a
    for i in range(18):
        if (dep[b]-dep[a]) & 1<<i:
            b=par[i][b]
    if a==b:
        return a
    for i in range(18)[::-1]:
        if par[i][a]!=par[i][b]:
            a=par[i][a]
            b=par[i][b]
    return par[0][a]

dfs(-1,0,0,0)

for i in range(17):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]

# LCAの準備が完了

ans = [0]*q
v_need = [[] for i in range(n)]
for i in range(q):
    x,y,u,v = map(int, input().split())
    x -= 1
    u -= 1
    v -= 1
    l = lca(u, v)
    # 色の情報がほしいのは u, v, lの3点
    # どのクエリに属するか, どの色を変えるか、距離はいくつにするか, 係数
    v_need[u].append((i, x, y, 1))
    v_need[v].append((i, x, y, 1))
    v_need[l].append((i, x, y, -2))

# 色が何回出たか
color = [0]*n
# その点までの各色の距離の総和
cdist = [0]*n

def dfs2(cur, par):
    for i, x, y, k in v_need[cur]:
        ans[i] += k*(dis[cur] - cdist[x] + y*color[x])
    for to, x, y, in edges[cur]:
        if to == par:
            continue
        color[x] += 1
        cdist[x] += y
        dfs2(to, cur)
        # オイラーツアーのように、戻ってきたら引く
        # これによって、a→b→c→b→dと移動した時a→b→dとみなせる
        color[x] -= 1
        cdist[x] -= y
dfs2(0, -1)

for i in ans:
    print(i)