Nhảy Xuống Lá

Cho một cây $n$ đỉnh, được gốc hóa tại đỉnh $1$. Mỗi đỉnh $i$ có hai số nguyên $a_i$ và $b_i$.

Từ một đỉnh $u$ không phải lá, bạn được nhảy thẳng tới một đỉnh $v$ bất kỳ là hậu duệ nghiêm ngặt của $u$, tức $v$ nằm trong cây con của $u$ và $v\ne u$. Chi phí của bước nhảy là $a_u\cdot b_v$. Từ $v$, bạn tiếp tục nhảy theo cùng quy tắc cho đến khi tới một lá.

Một đỉnh khác gốc là lá khi nó không có con. Đỉnh gốc $1$ không được xem là lá nếu cây có nhiều hơn một đỉnh, kể cả khi bậc của nó bằng $1$.

Với mỗi đỉnh $u$, hãy tìm tổng chi phí nhỏ nhất để bắt đầu tại $u$ và kết thúc ở một lá trong cây con của $u$. Với một đỉnh lá, chi phí bằng $0$ vì không cần thực hiện bước nhảy nào.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa $n$ số nguyên $b_1,b_2,\dots ,b_n$.
• Trong $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$, mô tả một cạnh của cây.

Output

• In $n$ số nguyên trên một dòng. Số thứ $u$ là chi phí nhỏ nhất khi bắt đầu tại đỉnh $u$.

Constraints

• $2\le n\le 10^5$.
• $|a_i|,|b_i|\le 10^5$.
• Các cạnh tạo thành một cây.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 60$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6
4 -2 3 5 1 7
2 6 -1 4 3 -5
1 2
1 3
2 4
2 5
3 6

-20 -8 -15 0 0 0