Bạn đang mắc kẹt trong một mê cung gồm ~n~ căn phòng, được đánh số từ ~1~ đến ~n~. Mê cung này có cấu trúc dạng cây, với phòng số ~1~ là gốc.

Phòng thứ ~i~ có hai giá trị đặc biệt: ~a_i~ và ~b_i~. Từ phòng ~u~, bạn có thể nhảy đến bất kì phòng nào nằm trong cây con gốc ~u~, trừ chính đỉnh ~u~. Chi phí để nhảy từ phòng ~x~ đến ~y~ là ~a_x \cdot b_y~.

Nhiệm vụ của bạn là với mọi phòng ~u~, tính chi phí nhỏ nhất để thoát khỏi mê cung nếu xuất phát từ đỉnh ~u~ và kết thúc tại một nút lá (là một nút có bậc bằng ~1~, trừ nút gốc) bất kì.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~2 \leq n \leq 10^5~) – số lượng đỉnh trong cây.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~-10^5 \leq a_i \leq 10^5~).

• Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~-10^5 \leq b_i \leq 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 \leq u_i, v_i \leq n~) mô tả cạnh giữa đỉnh ~u_i~ và ~v_i~ trong cây.

Output

In ra ~n~ số nguyên cách nhau bởi dấu cách, trong đó số thứ ~i~ là chi phí nhỏ nhất để đi từ nút ~i~ đến bất kỳ nút lá nào trong cây con gốc ~i~.

Scoring

Sample Input 1

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

Sample Output 1

10 50 0

Sample Input 2

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

Sample Output 2

-300 100 0 0

Notes

• Ở test ví dụ đầu tiên, nút ~3~ đã là lá nên chi phí của nó bằng ~0~. Với nút ~2~, ta nhảy thẳng đến nút ~3~ với chi phí ~a_2 \cdot b_3 = 50~. Với nút ~1~, ta nhảy thẳng đến nút ~3~ với chi phí ~a_1 \cdot b_3 = 10~.

• Ở test ví dụ thứ hai, nút ~3~ và ~4~ là lá, nên chi phí bằng ~0~. Với nút ~2~, ta nhảy đến nút ~4~ với chi phí ~a_2 \cdot b_4 = 100~. Với nút ~1~, ta nhảy từ ~1 \rightarrow 2 \rightarrow 4~ với chi phí ~a_1 \cdot b_2 + a_2 \cdot b_4 = -400+100=-300~.