Jumping

Cho một cây có \(n\) đỉnh (được đánh số từ \(1\) đến \(n\)) và có gốc tại đỉnh \(1\). Mỗi đỉnh đều có hai giá trị gắn liền với nó: \(a_i\) và \(b_i\) cho đỉnh thứ \(i\).

Bạn có thể nhảy từ một đỉnh đến bất kỳ đỉnh nào trong cây con của nó. Chi phí cho một lần nhảy từ đỉnh \(x\) đến đỉnh \(y\) là tích của \(a_x\) và \(b_y\). Tổng chi phí của một đường đi được tạo thành từ một hoặc nhiều lần nhảy là tổng chi phí của các lần nhảy riêng lẻ.

Với mỗi đỉnh, hãy tính toán tổng chi phí tối thiểu để đi đến một đỉnh lá bất kỳ từ đỉnh đó. Lưu ý rằng đỉnh gốc (đỉnh 1) không bao giờ được coi là đỉnh lá, ngay cả khi nó chỉ có một bậc (degree).

Bạn không thể nhảy từ một đỉnh đến chính nó.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 10^5\)) --- số lượng đỉnh trong cây.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^5 \le a_i \le 10^5\)).
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n\) (\(-10^5 \le b_i \le 10^5\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u_i\) và \(v_i\) (\(1 \le u_i, v_i \le n\)) mô tả một cạnh nối giữa hai đỉnh \(u_i\) và \(v_i\).

Output

In ra \(n\) số nguyên cách nhau bởi dấu cách. Số thứ \(i\) trong đó là chi phí tối thiểu để đi từ đỉnh \(i\) đến bất kỳ đỉnh lá nào.

Example

3
2 10 -1
7 -7 5
2 3
2 1

10 50 0 

4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3

-300 100 0 0 

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(N \leq 100\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có bậc của các đỉnh trong cây không vượt quá \(2\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại không có ràng buộc gì thêm.