Dane jest drzewo $T$ składające się z $N$ wierzchołków. Każda krawędź ma dodatnią wagę całkowitą. Wagę ścieżki $P$ w $T$ definiuje się jako sumę wag krawędzi należących do $P$ i oznacza jako $W(P)$.

Danych jest łącznie $Q$ zapytań, z których każde zawiera dwa wierzchołki $u$ i $v$ oraz dwie liczby całkowite $A$ i $B$. Dla każdego zapytania należy znaleźć dwie ścieżki proste $P_1$ oraz $P_2$ w $T$, spełniające następujące wymagania:

• $P_1$ i $P_2$ nie mają wspólnego wierzchołka.
• $P_1$ zaczyna się w $u$, a $P_2$ zaczyna się w $v$.
• Spośród wszystkich par $P_1$ i $P_2$ spełniających powyższe warunki, wartość $A \cdot W(P_1) + B \cdot W(P_2)$ powinna być zmaksymalizowana.

Dla każdego zapytania należy wypisać wartość $A \cdot W(P_1) + B \cdot W(P_2)$.

Wejście

W pierwszej linii znajdują się dwie oddzielone spacjami liczby całkowite $N$ i $Q$.

Każda z kolejnych $N - 1$ linii zawiera trzy oddzielone spacjami liczby całkowite $u, v, w$. Oznacza to, że w $T$ istnieje krawędź łącząca wierzchołki $u$ i $v$ o wadze $w$. Krawędzie te tworzą drzewo.

Każda z kolejnych $Q$ linii zawiera cztery oddzielone spacjami liczby całkowite $u, v, A, B$, określające pojedyncze zapytanie.

• $2 \leq N \leq 200\,000$
• $1 \leq Q \leq 500\,000$
• $1 \leq u < v \leq N$ dla krawędzi oraz zapytań
• $1 \leq w \leq 10\,000$
• $1 \leq A, B \leq 2 \cdot 10^9$

Wyjście

Dla każdego zapytania wypisz w pojedynczej linii liczbę całkowitą: maksymalną możliwą wartość $A \cdot W(P_1) + B \cdot W(P_2)$.

Przykład

Wejście 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

Wyjście 1

18
32
18
160