$N$ 個の頂点からなる木 $T$ が与えられる。各辺には正の整数重みがついている。木 $T$ におけるパス $P$ の重み $W(P)$ を、そのパスに含まれる辺の重みの総和と定義する。

合計 $Q$ 個のクエリが与えられる。各クエリは2つの頂点 $u, v$ と2つの整数 $A, B$ を含む。各クエリについて、以下の条件を満たす2つの単純パス $P_1, P_2$ を木 $T$ 上で見つけよ。

• $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)$ の値を出力せよ。

入力

1行目に、空白区切りの2つの整数 $N$ と $Q$ が与えられる。

続く $N - 1$ 行の各行には、空白区切りの3つの整数 $u, v, w$ が与えられる。これは、木 $T$ において頂点 $u$ と $v$ を結ぶ重み $w$ の辺が存在することを意味する。これらの辺は木を構成する。

続く $Q$ 行の各行には、空白区切りの4つの整数 $u, v, A, B$ が与えられ、1つのクエリを表す。

• $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行で出力せよ。

入出力例

入力 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