给定一棵包含 $N$ 个顶点的树 $T$。每条边都有一个正整数权值。树 $T$ 中路径 $P$ 的权值定义为路径上所有边的权值之和，记作 $W(P)$。

给定总共 $Q$ 次查询，每次查询包含两个顶点 $u$ 和 $v$，以及两个整数 $A$ 和 $B$。对于每次查询，你需要找到两条简单路径 $P_1$ 和 $P_2$，满足以下要求：

• $P_1$ 和 $P_2$ 不共享任何顶点。
• $P_1$ 的起点为 $u$，$P_2$ 的起点为 $v$。
• 在所有满足上述条件的 $P_1$ 和 $P_2$ 中，使得 $A \cdot W(P_1) + B \cdot W(P_2)$ 的值最大。

对于每次查询，输出 $A \cdot W(P_1) + B \cdot W(P_2)$ 的最大值。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $Q$。

接下来的 $N - 1$ 行，每行包含三个空格分隔的整数 $u, v, w$，表示树 $T$ 中存在一条连接顶点 $u$ 和 $v$ 的边，权值为 $w$。这些边构成了一棵树。

接下来的 $Q$ 行，每行包含四个空格分隔的整数 $u, v, A, B$，表示一次查询。

• $2 \le N \le 200\,000$
• $1 \le Q \le 500\,000$
• 对于边和查询，均满足 $1 \le u < v \le N$
• $1 \le w \le 10\,000$
• $1 \le A, B \le 2 \cdot 10^9$

输出格式

对于每次查询，输出一行一个整数，表示 $A \cdot W(P_1) + B \cdot W(P_2)$ 的最大可能值。

样例

输入 1

6 4
1 2 4
2 5 5
2 3 7
3 6 5
3 4 4
1 4 1 1
1 4 2 1
5 6 1 1
5 6 1 10

输出 1

18
32
18
160