Bạn được cho một cây $T$ gồm $N$ đỉnh. Mỗi cạnh có một trọng số là số nguyên dương. Trọng số của một đường đi $P$ trong $T$ được định nghĩa là tổng trọng số các cạnh trên $P$, ký hiệu là $W(P)$.

Bạn được cho tổng cộng $Q$ truy vấn, mỗi truy vấn chứa hai đỉnh $u$ và $v$, cùng hai số nguyên $A$ và $B$. Với mỗi truy vấn, bạn cần tìm hai đường đi đơn $P_1$ và $P_2$ trong $T$ thỏa mãn các điều kiện sau:

• $P_1$ và $P_2$ không có đỉnh chung.
• $P_1$ bắt đầu từ $u$, và $P_2$ bắt đầu từ $v$.
• Trong tất cả các cặp $P_1$ và $P_2$ thỏa mãn các điều kiện trên, giá trị $A \cdot W(P_1) + B \cdot W(P_2)$ phải được tối đa hóa.

Bạn cần xuất ra giá trị $A \cdot W(P_1) + B \cdot W(P_2)$ cho mỗi truy vấn.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ cách nhau bởi dấu cách.

Mỗi dòng trong $N - 1$ dòng tiếp theo chứa ba số nguyên $u, v, w$ cách nhau bởi dấu cách. Điều này có nghĩa là có một cạnh trong $T$ nối hai đỉnh $u$ và $v$ với trọng số $w$. Các cạnh này tạo thành một cây.

Mỗi dòng trong $Q$ dòng tiếp theo chứa bốn số nguyên $u, v, A, B$ cách nhau bởi dấu cách, biểu thị một truy vấn.

• $2 \le N \le 200\,000$
• $1 \le Q \le 500\,000$
• $1 \le u < v \le N$ cho cả cạnh và truy vấn
• $1 \le w \le 10\,000$
• $1 \le A, B \le 2 \cdot 10^9$

Dữ liệu ra

Với mỗi truy vấn, xuất ra một dòng duy nhất chứa một số nguyên: giá trị lớn nhất có thể của $A \cdot W(P_1) + B \cdot W(P_2)$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

18
32
18
160