Hài hòa

Cho một cây gồm \(n\) đỉnh. Với mỗi đỉnh \(i\), ta biết hai giá trị:

• \(c_i\): giá trị của đỉnh nếu được tô màu đỏ;
• \(p_i\): giá trị của đỉnh nếu được tô màu xanh.

Xét đường đi ngắn nhất từ một đỉnh \(A\) đến một đỉnh \(B\) trên cây. Khi duyệt theo thứ tự các đỉnh trên đường đi, mỗi đỉnh được chọn một trong hai màu: đỏ hoặc xanh.

Một đường đi được gọi là hài hòa nếu trong suốt quá trình duyệt đường đi, tại mọi thời điểm, không màu nào "áp đảo" màu còn lại. Cụ thể, màu đỏ hoặc xanh được coi là áp đảo nếu nó xuất hiện ít nhất 3 lần nhiều hơn màu còn lại.

Giá trị của đường đi là tổng các giá trị nhận được từ các đỉnh theo màu được chọn.

Với mỗi truy vấn gồm hai đỉnh \(u\) và \(v\), hãy tìm giá trị lớn nhất có thể của một đường đi hài hòa từ \(u\) đến \(v\). Đảm bảo rằng luôn tồn tại ít nhất một cách tô hợp lệ.

\InputFile
\begin itemize

• Dòng đầu chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên \(c_i\) (\(-10^9 \le c_i \le 10^9\)).

• Dòng thứ ba chứa \(n\) số nguyên \(p_i\) (\(-10^9 \le p_i \le 10^9\)).

• Tiếp theo là \(n-1\) dòng, mỗi dòng chứa hai số \(u\) và \(v\) biểu thị một cạnh của cây.

• Tiếp theo là \(q\) dòng, mỗi dòng chứa hai số \(u, v\) --- truy vấn cần trả lời.

\OutputFile

Với mỗi truy vấn, in ra giá trị lớn nhất có thể của một đường đi hài hòa từ \(u\) đến \(v\).

\Scoring

• Subtask 1 (15 điểm): \(n, q \le 15\).
• Subtask 2 (34 điểm): \(n, q \le 1000\).
• Subtask 3 (19 điểm): \(q \le 1000\).
• Subtask 4 (32 điểm): Không có ràng buộc bổ sung.

Example

5 3
2 -1 3 -1 2
-5 -4 -1 -5 -4
5 2
5 3
5 4
5 1
2 4
4 5
3 3

-3
1
3

5 3
-4 0 -5 -5 5
5 5 -4 2 2
1 5
2 3
3 4
1 3
5 4
2 5
2 4

8
10
2