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
sys.setrecursionlimit(10**6+1) #再帰関数の上限,10**5以上の場合python


def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None


#N, Q = map(int, input().split())
N, Q = map(int, input().split())
#A = tuple(map(int, input().split())) #1行ベクトル
#L = tuple(int(input()) for i in range(N)) #改行ベクトル
#S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

edge = [[] for i in range(N)]
for i in range(N-1):#木の場合M=N-1
    a,b,c,w = map(int,input().split())
    edge[a-1].append((b-1,c-1,w))
    edge[b-1].append((a-1,c-1,w)) #有向のばあいコメントアウト



#ダブリングによるLCA, 前処理NlogN, 呼び出しlogN, 安定  
def dfs(start):
    q=[(start,-1,0,0)]
    pars=[-1]*N
    depth=[-1]*N
    dist=[-1]*N
    while len(q):
        e,p,d,dis=q.pop()#ここをpopleftにすると幅優先探索BFSになる
        if depth[e]!=-1:continue
        pars[e]=p
        depth[e]=d
        dist[e]=dis
        for ne,c,w in edge[e]:
            q.append((ne,e,d+1,dis+w))
    return pars,depth,dist
pars,d,dist=dfs(0)
ln=N.bit_length()
dp=[[-1]*N for _ in range(ln+1)]
dp[0]=pars
for i in range(1,ln+1):
    for j in range(N):
        dp[i][j]=dp[i-1][dp[i-1][j]]


# LCAの計算
def lca(u, v):
    du = d[u]; dv = d[v]
    if du > dv:
        du, dv = dv, du
        u,v=v,u
    dif=dv-du
    for i in range(ln+1):
        if (dif>>i)&1:
            v=dp[i][v]
    if u==v:return u
    for i in range(ln,-1,-1):
        pu=dp[i][u];pv=dp[i][v]
        if pu!=pv:
            u,v=pu,pv
    return pars[u]

q=Q
qs = tuple(tuple(map(int, input().split())) for i in range(Q)) #改行行列
ans=[0]*Q
qn=[[] for _ in range(N)]
for i,(x,y,u,v) in enumerate(qs):
    ans[i]=dist[u-1]+dist[v-1]-2*dist[lca(u-1,v-1)]
    qn[u-1].append((i,x-1,y,1))
    qn[v-1].append((i,x-1,y,1))
    qn[lca(u-1,v-1)].append((i,x-1,y,-2))
cnt=[0]*Q
#printe(qn)

qc=[[0,0] for _ in range(Q)]
cc=[[0,0] for _ in range(N-1)]

dfq=[(0,None,0,-1)]
def dfs2(e):
    for qi,x,y,sgn in qn[e]:
        ans[qi]+=(y*cc[x][0]-cc[x][1])*sgn
    for ne,c,nd in edge[e]:
        if ne==pars[e]:continue
        if c!=None:
            cc[c][0]+=1
            cc[c][1]+=nd
        dfs2(ne)
        if c!=None:
            cc[c][0]-=1
            cc[c][1]-=nd
dfs2(0)
printl(ans)

# n=N
# A = [0]*q
# C = [[] for _ in range(n)]
# num = [0]*n
# cum = [0]*n
# for i in range(q):
#   x, y, u, v = map(int, input().split())
#   u -= 1
#   v -= 1
#   a = lca(u, v)
#   C[u].append((i, x, y, 1))
#   C[v].append((i, x, y, 1))
#   C[a].append((i, x, y, -2))
# dist = 0
# stack = [0]
# def dfs2(v):
#   global dist
#   for i, x, y, b in C[v]:
#     A[i] += (dist + num[x]*y - cum[x]) * b
#   for nv, c, d in edge[v]:
#     c+=1
#     if nv ==pars[v]:continue
#     dist += d
#     num[c] += 1
#     cum[c] += d
#     dfs2(nv)
#     dist -= d
#     num[c] -= 1
#     cum[c] -= d
# dfs2(0)
# print(*A, sep="\n")