Vous disposez d'un arbre $T$ composé de $N$ sommets. Chaque arête possède un poids entier positif. Le poids d'un chemin $P$ dans $T$ est défini comme la somme des poids des arêtes de $P$, notée $W(P)$.

Vous recevez un total de $Q$ requêtes, chacune contenant deux sommets, $u$ et $v$, ainsi que deux entiers, $A$ et $B$. Pour chaque requête, vous devez trouver deux chemins simples $P_1$ et $P_2$ dans $T$ satisfaisant les conditions suivantes :

• $P_1$ et $P_2$ ne partagent aucun sommet.
• $P_1$ part de $u$ et $P_2$ part de $v$.
• Parmi tous les $P_1$ et $P_2$ satisfaisant les conditions ci-dessus, la valeur de $A \cdot W(P_1) + B \cdot W(P_2)$ doit être maximisée.

Vous devez afficher la valeur de $A \cdot W(P_1) + B \cdot W(P_2)$ pour chaque requête.

Entrée

La première ligne contient deux entiers séparés par des espaces $N$ et $Q$.

Chacune des $N - 1$ lignes suivantes contient trois entiers séparés par des espaces $u$, $v$, $w$. Cela signifie qu'il existe une arête dans $T$ reliant les sommets $u$ et $v$ avec un poids $w$. Ensemble, ces arêtes forment un arbre.

Chacune des $Q$ lignes suivantes contient quatre entiers séparés par des espaces $u$, $v$, $A$, $B$, désignant une seule requête.

• $2 \leq N \leq 200\,000$
• $1 \leq Q \leq 500\,000$
• $1 \leq u < v \leq N$ pour les arêtes et les requêtes
• $1 \leq w \leq 10\,000$
• $1 \leq A, B \leq 2 \cdot 10^9$

Sortie

Pour chaque requête, affichez une seule ligne contenant un entier : la valeur maximale possible de $A \cdot W(P_1) + B \cdot W(P_2)$.

Exemples

Entrée 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

Sortie 1

18
32
18
160