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(10**6+1) #再帰関数の上限,10**5以上の場合python\n\n\ndef input(): \n    x=sys.stdin.readline()\n    return x[:-1] if x[-1]=="\\n" else x\ndef printe(*x):print("## ",*x,file=sys.stderr)\ndef printl(li): _=print(*li, sep="\\n") if li else None\n\n\n#N, Q = map(int, input().split())\nN, Q = map(int, input().split())\n#A = tuple(map(int, input().split())) #1行ベクトル\n#L = tuple(int(input()) for i in range(N)) #改行ベクトル\n#S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列\n\nedge = [[] for i in range(N)]\nfor i in range(N-1):#木の場合M=N-1\n    a,b,c,w = map(int,input().split())\n    edge[a-1].append((b-1,c-1,w))\n    edge[b-1].append((a-1,c-1,w)) #有向のばあいコメントアウト\n\n\n\n#ダブリングによるLCA, 前処理NlogN, 呼び出しlogN, 安定  \ndef dfs(start):\n    q=[(start,-1,0,0)]\n    pars=[-1]*N\n    depth=[-1]*N\n    dist=[-1]*N\n    while len(q):\n        e,p,d,dis=q.pop()#ここをpopleftにすると幅優先探索BFSになる\n        if depth[e]!=-1:continue\n        pars[e]=p\n        depth[e]=d\n        dist[e]=dis\n        for ne,c,w in edge[e]:\n            q.append((ne,e,d+1,dis+w))\n    return pars,depth,dist\npars,d,dist=dfs(0)\nln=N.bit_length()\ndp=[[-1]*N for _ in range(ln+1)]\ndp[0]=pars\nfor i in range(1,ln+1):\n    for j in range(N):\n        dp[i][j]=dp[i-1][dp[i-1][j]]\n\n\n# LCAの計算\ndef lca(u, v):\n    du = d[u]; dv = d[v]\n    if du > dv:\n        du, dv = dv, du\n        u,v=v,u\n    dif=dv-du\n    for i in range(ln+1):\n        if (dif>>i)&1:\n            v=dp[i][v]\n    if u==v:return u\n    for i in range(ln,-1,-1):\n        pu=dp[i][u];pv=dp[i][v]\n        if pu!=pv:\n            u,v=pu,pv\n    return pars[u]\n\nq=Q\n#qs = tuple(tuple(map(int, input().split())) for i in range(Q)) #改行行列\n# ans=[0]*Q\n# qn=[[] for _ in range(N)]\n# for i,(x,y,u,v) in enumerate(qs):\n#     ans[i]=dist[u-1]+dist[v-1]-dist[lca(u-1,v-1)]\n#     qn[u-1].append((i,x-1,y))\n#     qn[v-1].append((i,x-1,y))\n# cnt=[0]*Q\n# #printe(qn)\n\n# qc=[[0,0] for _ in range(Q)]\n# cc=[[0,0] for _ in range(N-1)]\n\n# dfq=[(0,None,0,-1)]\n# def dfs2(e,c,d,p):\n#     if c!=None:\n#         cc[c][0]+=1\n#         cc[c][1]+=d\n#     for qi,x,y in qn[e]:\n#         if cnt[qi]==0:\n#             qc[qi][0]-=cc[x][0]\n#             qc[qi][1]-=cc[x][1]\n#         elif cnt[qi]==1:\n#             qc[qi][0]+=cc[x][0]\n#             qc[qi][1]+=cc[x][1]\n#             ans[qi]+=y*qc[qi][0]-qc[qi][1]\n#         cnt[qi]+=1\n#     for ne,nc,nd in edge[e]:\n#         if ne==par[e]:continue\n#         dfs2(ne,nc,nd,e)\n#     if c!=None:\n#         cc[c][0]+=1\n#         cc[c][1]+=d\n# dfs2(0)\n# printl(ans)\nn=N\nA = [0]*q\nC = [[] for _ in range(n)]\nnum = [0]*n\ncum = [0]*n\nfor i in range(q):\n  x, y, u, v = map(int, input().split())\n  u -= 1\n  v -= 1\n  a = lca(u, v)\n  C[u].append((i, x, y, 1))\n  C[v].append((i, x, y, 1))\n  C[a].append((i, x, y, -2))\ndist = 0\nstack = [0]\ndef dfs2(v):\n  nonlocal dist\n  for i, x, y, b in C[v]:\n    A[i] += (dist + num[x]*y - cum[x]) * b\n  for nv, c, d in edge[v]:\n    c+=1\n    if nv ==pars[v]:continue\n    dist += d\n    num[c] += 1\n    cum[c] += d\n    dfs2(nv)\n    dist -= d\n    num[c] -= 1\n    cum[c] -= d\ndfs2(0)\nprint(*A, sep="\\n")'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: