题目描述

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.)

有一棵树，其顶点编号为 $N$ 至 $N$ 。这棵树上的 $i$ 条边连接顶点 $a_i$ 和顶点 $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$
$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$

输出格式

打印 $Q$ 行。 $j$ （ $1 \leq j \leq Q$ ）行应包含查询 $j$ 的答案。

样例 #1

样例输入 #1

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

样例输出 #1

130
200
60

说明

数据规模与约定

• $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 \lt v_j \leq N$
• 给定图形是一棵树。
• 输入值均为整数。

样例 $1$ 解释

该输入的图形如下

颜色 $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$ 的边现在具有原来的长度。