Given a undirected tree containing N nodes where i^th node has value \( a(i) \). Let us define cost of the tree as C, where
\( C = \sum_{i=1}^N f(i) \)
\( f(i)=\sum_j g(j) ;where \hspace{0.25cm} j \hspace{0.25cm} \epsilon \hspace{0.25cm} subtree \hspace{0.25cm} of \hspace{0.25cm} i \)
\( g(j)=\sum_k a(k) ;where \hspace{0.25cm} k \hspace{0.25cm} \epsilon \hspace{0.25cm} subtree \hspace{0.25cm} of \hspace{0.25cm} j \)
Find a root of the tree such that the cost of the tree is minimum.

Input

The first line of input contains N (1 ≤ N ≤ 100,000) - the number of nodes in the tree.
The second line contains N integers a₁, a₂, ..., a_N, where a_i (1 ≤ a_i ≤ \(10^6\)) is the value stored at the i^th node.
The next N-1 lines contains two integers u and v, meaning that there is an edge connecting u and v.

Output

Print two integers, the root of the tree such that the cost of tree is minimum and minimum cost. If there are multiple possible values of root, print the minimum one.

Constraints

\( 1 \leq N \leq 1000, 1 \leq a(i) \leq 10^6 \) in 40% of test cases.
\( 1 \leq N \leq 10^5, 1 \leq a(i) \leq 10^6 \) in 60% of test cases.

NOTE: The value of C will fit in 64-bit integer.