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
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

class LCA:
    def __init__(self, edge, root):
        self.l = len(edge)
        self.stack = []
        self.stack.append((root, 0))
        self.vs = []
        self.depth = [0]*self.l
        self.firstVisited = [-1]*self.l
        while self.stack:
            v, d = self.stack[-1]
            if self.firstVisited[v] == -1:
                self.firstVisited[v] = len(self.vs)
            self.vs.append(v)
            self.depth[v] = d
            if edge[v]:
                self.stack.append((edge[v].pop(), d+1))
            else:
                self.stack.pop()
        
        self.n = len(self.vs)
        self.INF = (self.l, self.l)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, v in enumerate(self.vs, self.N0):
            self.seg[i] = (self.depth[v], v)
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = min(self.seg[2*i], self.seg[2*i+1])
    
    def _query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = min(res, self.seg[r-1])
            if l & 1:
                res = min(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res

    def query(self, u, v):
        fu, fv = self.firstVisited[u], self.firstVisited[v]
        if fu > fv:
            fu, fv = fv, fu
        return self._query(fu, fv+1)[1]

n, q = map(int, input().split())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b, c, d = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append((b, c, d))
  T[b].append((a, c, d))
G = [[] for _ in range(n)]
edge = [[] for _ in range(n)]
stack = [(0, -1)]
while stack:
  v, par = stack.pop()
  for nv, c, d in T[v]:
    if nv == par:
      continue
    G[v].append((nv, c, d))
    edge[v].append(nv)
    stack.append((nv, v))

seg = LCA(edge, 0)
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 = seg.query(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 dfs(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 G[v]:
    dist += d
    num[c] += 1
    cum[c] += d
    dfs(nv)
    dist -= d
    num[c] -= 1
    cum[c] -= d
dfs(0)
print(*A, sep="\n")