EIU Programming Practices and Exams

Cho dữ liệu mô tả cây, hãy viết chương trình tìm đỉnh có chỉ số nhỏ nhất làm gốc và thỏa mãn các điều kiện sau:

• Đỉnh gốc có đúng 2 nhánh con, mỗi nhánh có ít nhất một node.
• Gọi TW1 là tổng trọng số của nhánh con thứ nhất, TW2 là tổng trọng số của nhánh con thứ hai, thì |TW1 – TW2| có giá trị nhỏ nhất.

Input

Dòng đầu tiên là số node của cây N (0 < N ≤ 10⁵). Các node được đánh số từ 1 đến N.

Dòng tiếp theo chứa N số nguyên w_i (0 < w_i ≤ 10⁹), là trọng số của node thứ i.

Dòng thứ i trong N-1 dòng tiếp theo gồm 2 số nguyên u_i, v_i cho biết có cạnh nối u_i và v_i

* 80% Testcases có N không vượt quá 1000

Output

In ra chỉ số của đỉnh gốc và tổng trọng số của hai nhánh con theo thứ tự tăng dần. Nếu không tồn tại đỉnh gốc, in ra -1.

Example

Input:
4
2 3 1 4
1 2
1 3
2 4

Output:
2 3 4