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.

-----Sample 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

-----Sample Output-----
130
200
60

The graph in this input is as follows:

Here the edges of Color 1 are shown as solid red lines, the edge of Color 2 is shown as a bold green line, and the edge of Color 4 is shown as a blue dashed line.
 - Query 1: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 4 is 100 + 30 = 130.
 - Query 2: Assuming that the length of every edge whose color is 1 is changed to 100, the distance between Vertex 1 and Vertex 5 is 100 + 100 = 200.
 - Query 3: Assuming that the length of every edge whose color is 3 is changed to 1000 (there is no such edge), the distance between Vertex 3 and Vertex 4 is 20 + 10 + 30 = 60. Note that the edges of Color 1 now have their original lengths.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\nsys.setrecursionlimit(2147483647)\nINF=float("inf")\nMOD=10**9+7\ninput=lambda :sys.stdin.readline().rstrip()\nclass LCA(object):\n    def __init__(self,E,root=0):\n        self.__n=len(E)\n        self.__E=E\n        self.__logn=(self.__n-1).bit_length()\n        self.__depth=[-1]*self.__n\n        self.__dist=[-1]*self.__n\n        self.__depth[root]=0\n        self.__dist[root]=0\n        self.__parents=[[-1]*self.__n for _ in range(self.__logn)]\n        self.__dfs(root)\n        self.__doubling()\n\n    def __dfs(self,v):\n        for u,c,d in self.__E[v]:\n            if(self.__depth[u]!=-1): continue\n            self.__parents[0][u]=v\n            self.__depth[u]=self.__depth[v]+1\n            self.__dist[u]=self.__dist[v]+d\n            self.__dfs(u)\n\n    def __doubling(self):\n        for i in range(1,self.__logn):\n            for v in range(self.__n):\n                if(self.__parents[i-1][v]==-1): continue\n                self.__parents[i][v]=self.__parents[i-1][self.__parents[i-1][v]]\n\n    @property\n    def depth(self):\n        return self.__depth\n\n    @property\n    def dist(self):\n        return self.__dist\n\n    def get(self,u,v):\n        dd=self.__depth[v]-self.__depth[u]\n        if(dd<0): # vの方が深いようにする\n            u,v=v,u\n            dd*=-1\n        for i in range(self.__logn):\n            if(dd&(1<<i)): v=self.__parents[i][v]\n        if(v==u): return v\n        for i in range(self.__logn-1,-1,-1):\n            pu,pv=self.__parents[i][u],self.__parents[i][v]\n            if(pu!=pv): u,v=pu,pv\n        return self.__parents[0][u]\n\ndef resolve():\n    n,q=map(int,input().split())\n    E=[[] for _ in range(n)]\n    for _ in range(n-1):\n        a,b,c,d=map(int,input().split())\n        a-=1; b-=1\n        E[a].append((b,c,d))\n        E[b].append((a,c,d))\n    G=LCA(E)\n\n    # Queryを先読みする\n    Qs=[[] for _ in range(n)] #Q[v]: idx, color, mag, coef\n    for i in range(q):\n        x,y,u,v=map(int,input().split())\n        u-=1; v-=1\n        c=G.get(u,v)\n        Qs[u].append((i,x,y,1))\n        Qs[v].append((i,x,y,1))\n        Qs[c].append((i,x,y,-2))\n\n    # dfsでクエリに答えていく\n    ans=[0]*q\n    S=[[0,0] for _ in range(n)] # S[col]: total num, total len\n    def dfs(v,p):\n        # クエリに答える\n        # 現在のlengthから、色のtotal lenを引き、青の個数*倍率(mug)を足したものが変更後の長さ\n        for idx,col,mag,coef in Qs[v]:\n            x=G.dist[v]\n            x-=S[col][1]\n            x+=mag*S[col][0]\n            ans[idx]+=x*coef\n        # 遷移\n        for nv,col,d in E[v]:\n            if(nv==p): continue\n            S[col][0]+=1\n            S[col][1]+=d\n            dfs(nv,v)\n            S[col][0]-=1\n            S[col][1]-=d\n    dfs(0,-1)\n    print(*ans,sep="\\n")\nresolve()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 19097