Along with the lights Andrew purchased, he has also selected a Christmas tree. Unfortunately, it appears that Andrew is not the best at picking trees as his tree starts to deteriorate when he tries to decorate it, each branch snapping one by one. Andrew decides to not let this bring down his holiday cheer and copes with the horrible situation by turning it into a algorithmic puzzle. Since Andrew is quite an extreme man, he likes to observe extreme values. Each of the ~N~ nodes in his tree is associated with a value ~a_i~. With each branch break, the tree splits into separate components. The range of a component is defined to be the difference between the maximum and minimum values of the nodes in that component. Andrew would like to know the maximum range across all components after every branch break. You, being Andrew's only friend, need to use your vast algorithmic knowledge to assist him in solving this problem.

Input Specification

The first line contains one integer ~N~ ~(1 \leq N \leq 2\cdot10^5)~, the number of nodes in Andrew's tree.

The second line contains ~N~ space separated integers, ~a_i~ ~(1 \leq a_i \leq 10^9)~, the value of the ~i^{th}~ node.

The next ~N-1~ lines each contains two integers, ~u_i~ and ~v_i~ ~(1\leq u_i, v_i \leq N)~, the indicating that nodes ~u_i~ and node ~v_i~ are connected by the ~i^{th}~ branch.

The final line contains ~N-1~ space separated integers, the order in which the branches will break.

Output Specification

Output ~N~ space separated integers, the intial range of the tree before any branch breaks, as well as the maximum component range after each of the ~N-1~ branch breaks.

Subtasks

Subtask 1 [10%]

~1 \leq N,a_i \le 100~

Subtask 2 [90%]

No further constraints.

Sample Input

6
1 2 3 4 5 6
6 1
1 2
5 1
4 2
1 3
1 5 2 3 4

Sample Output

5 4 4 4 2 0

Sample Explanation

The branches break in the order ~6-1~, ~1-3~, ~1-2~, ~5-1~, and ~4-2~.

The inital range of the tree before any branch breaks is ~5~ as the maximum value is ~6~ and the minimum value is ~1~. After the first branch break which separates nodes ~1~ and ~6~, the tree splits into separate components ~(1,2,3,4,5)~ and ~(6)~. The range of ~(1,2,3,4,5)~ is ~4~ which is greater compared to the range of ~(6)~, ~0~. After the second branch break which separates nodes ~1~ and ~3~, the components are now ~(1,2,4,5)~, ~(3)~, and ~(6)~. The maximum range is still ~4~. This process continues until all nodes are their own separate component.