题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为$1$到 $N$。

树上的第$i$条边连接 Vertex $a_i$和 Vertex$b_i$，边的颜色和长度分别为 $c_i$ 和 $d_i$。

这里，每条边的颜色用大于等于$1$小于等于 $N -1$的整数表示。同一个整数对应相同的颜色，不同的整数对应不同的颜色。

回答以下 Q 个查询:

査询 $j(1 \leq j \leq Q)$:假设颜色为$x_j$的每条边的长度都改变为 $y_j$，找出顶点 $u_j$和顶点$v_j$之间的距离。(边的长度的改变不会影响后续的查询。)

输入

第一行两个整数$N,Q$ 接下来一共$N-1$行，表示$a_i,b_i,c_i,d_i$

接下来一共$Q$个询问$x_i,y_i,u_i,v_i$

输出

输出$Q$行，第$j$行$(1≤ j< Q)$应该包含查询 $j$的答案。

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

130
200
60

样例解释

此例的图如下所示：

这里，颜色为1的边是实线红色，颜色为2的边是粗体绿色，颜色为 4 的边是蓝色虚线。

查询 1:假设颜色为 1的每条边的长度都改变为 100，那么顶点1和顶点 4之间的距离为 100 + 30 = 130。

查询 2:假设颜色为1的每条边的长度都改变为 100，那么顶点1和顶点5之间的距离为 100 + 100 = 200.

查询 3:假设颜色为3的每条边的长度都改变为 1000(这样的边不存在)，那么顶点3和顶点4之间的距离为20+ 10 + 30 = 60。注意，颜色为 1 的边现在恢复了原始长度。

提示

$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 c_j \leq N-1$

$1 \leq y_j \leq 10^4$

$1 \leq u_j < v_j \leq N$

给定的图是一棵树