給定一棵包含 $N$ 個頂點的樹 $T$。每條邊都有一個正整數權重。樹 $T$ 中路徑 $P$ 的權重定義為該路徑上所有邊的權重總和，記作 $W(P)$。

給定總共 $Q$ 筆詢問，每筆詢問包含兩個頂點 $u$ 與 $v$，以及兩個整數 $A$ 與 $B$。對於每筆詢問，你需要找到兩條在 $T$ 中的簡單路徑 $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