Se te da un árbol $T$ que consiste en $N$ vértices. Cada arista tiene un peso entero positivo. El peso de un camino $P$ en $T$ se define como la suma de los pesos de las aristas en $P$, denotado por $W(P)$.

Se te da un total de $Q$ consultas, cada una conteniendo dos vértices, $u$ y $v$, y dos enteros, $A$ y $B$. Para cada consulta, debes encontrar dos caminos simples $P_1$ y $P_2$ en $T$ que satisfagan los siguientes requisitos:

• $P_1$ y $P_2$ no comparten ningún vértice.
• $P_1$ comienza en $u$, y $P_2$ comienza en $v$.
• Entre todos los $P_1$ y $P_2$ que satisfacen las condiciones anteriores, el valor de $A \cdot W(P_1) + B \cdot W(P_2)$ debe ser maximizado.

Debes imprimir el valor de $A \cdot W(P_1) + B \cdot W(P_2)$ para cada consulta.

Entrada

La primera línea contiene dos enteros separados por espacios $N$ y $Q$.

Cada una de las siguientes $N - 1$ líneas contiene tres enteros separados por espacios $u$, $v$, $w$. Esto significa que hay una arista en $T$ que conecta los vértices $u$ y $v$ con peso $w$. Juntas, estas aristas forman un árbol.

Cada una de las siguientes $Q$ líneas contiene cuatro enteros separados por espacios $u$, $v$, $A$, $B$, denotando una única consulta.

• $2 \le N \le 200\,000$
• $1 \le Q \le 500\,000$
• $1 \le u < v \le N$ tanto para las aristas como para las consultas
• $1 \le w \le 10\,000$
• $1 \le A, B \le 2 \cdot 10^9$

Salida

Para cada consulta, imprime una sola línea con un entero: el valor máximo posible de $A \cdot W(P_1) + B \cdot W(P_2)$.

Ejemplos

Entrada 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

Salida 1

18
32
18
160