Дано дерево $T$, состоящее из $N$ вершин. Каждое ребро имеет положительный целочисленный вес. Вес пути $P$ в $T$ определяется как сумма весов рёбер в $P$ и обозначается $W(P)$.

Вам дано $Q$ запросов, каждый из которых содержит две вершины $u$ и $v$, а также два целых числа $A$ и $B$. Для каждого запроса необходимо найти два простых пути $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)$.

Входные данные

Первая строка содержит два целых числа $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