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]-dist[lca(u-1,v-1)]
#     qn[u-1].append((i,x-1,y))
#     qn[v-1].append((i,x-1,y))
# 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,c,d,p):
#     if c!=None:
#         cc[c][0]+=1
#         cc[c][1]+=d
#     for qi,x,y in qn[e]:
#         if cnt[qi]==0:
#             qc[qi][0]-=cc[x][0]
#             qc[qi][1]-=cc[x][1]
#         elif cnt[qi]==1:
#             qc[qi][0]+=cc[x][0]
#             qc[qi][1]+=cc[x][1]
#             ans[qi]+=y*qc[qi][0]-qc[qi][1]
#         cnt[qi]+=1
#     for ne,nc,nd in edge[e]:
#         if ne==par[e]:continue
#         dfs2(ne,nc,nd,e)
#     if c!=None:
#         cc[c][0]+=1
#         cc[c][1]+=d
# 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")