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(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class LCA(object):
    def __init__(self,E,root=0):
        self.__n=len(E)
        self.__E=E
        self.__logn=(self.__n-1).bit_length()
        self.__depth=[-1]*self.__n
        self.__dist=[-1]*self.__n
        self.__depth[root]=0
        self.__dist[root]=0
        self.__parents=[[-1]*self.__n for _ in range(self.__logn)]
        self.__dfs(root)
        self.__doubling()

    def __dfs(self,v):
        for u,c,d in self.__E[v]:
            if(self.__depth[u]!=-1): continue
            self.__parents[0][u]=v
            self.__depth[u]=self.__depth[v]+1
            self.__dist[u]=self.__dist[v]+d
            self.__dfs(u)

    def __doubling(self):
        for i in range(1,self.__logn):
            for v in range(self.__n):
                if(self.__parents[i-1][v]==-1): continue
                self.__parents[i][v]=self.__parents[i-1][self.__parents[i-1][v]]

    @property
    def depth(self):
        return self.__depth

    @property
    def dist(self):
        return self.__dist

    def get(self,u,v):
        dd=self.__depth[v]-self.__depth[u]
        if(dd<0): # vの方が深いようにする
            u,v=v,u
            dd*=-1
        for i in range(self.__logn):
            if(dd&(1<<i)): v=self.__parents[i][v]
        if(v==u): return v
        for i in range(self.__logn-1,-1,-1):
            pu,pv=self.__parents[i][u],self.__parents[i][v]
            if(pu!=pv): u,v=pu,pv
        return self.__parents[0][u]

def resolve():
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b,c,d=map(int,input().split())
        a-=1; b-=1
        E[a].append((b,c,d))
        E[b].append((a,c,d))
    G=LCA(E)

    # Queryを先読みする
    Qs=[[] for _ in range(n)] #Q[v]: idx, color, mag, coef
    for i in range(q):
        x,y,u,v=map(int,input().split())
        u-=1; v-=1
        c=G.get(u,v)
        Qs[u].append((i,x,y,1))
        Qs[v].append((i,x,y,1))
        Qs[c].append((i,x,y,-2))

    # dfsでクエリに答えていく
    ans=[0]*q
    S=[[0,0] for _ in range(n)] # S[col]: total num, total len
    def dfs(v,p):
        # クエリに答える
        # 現在のlengthから、色のtotal lenを引き、青の個数*倍率(mug)を足したものが変更後の長さ
        for idx,col,mag,coef in Qs[v]:
            x=G.dist[v]
            x-=S[col][1]
            x+=mag*S[col][0]
            ans[idx]+=x*coef
        # 遷移
        for nv,col,d in E[v]:
            if(nv==p): continue
            S[col][0]+=1
            S[col][1]+=d
            dfs(nv,v)
            S[col][0]-=1
            S[col][1]-=d
    dfs(0,-1)
    print(*ans,sep="\n")
resolve()