You are given a tree containing $$N$$ nodes(numbered from $$1$$ to $$N$$) and each node has a value associated with it. We define **'special value'** of any graph as the maximum absolute difference of values of any two nodes such that there exists a path between them. Now you are given $$N-1$$ integers denoting that you have to delete i^{th} edge at the i^{th} step and find the 'special value' of the graph thus formed.

**INPUT:**

First line constains an integer $$N$$-number of nodes.

Next $$N-1$$ lines contains two integers $$u$$ $$v$$ denoting that there is a bidirectional edge between node $$u$$ and $$v$$

Next line contains $$N$$ integers i^{th} of which is the value of node i.

Next $$N-1$$ lines contains an integer $$x$$ where the i^{th} line denotes the index of the edge to be deleted at i^{th} step.

**Note:** Every edge will be deleted exactly once.

**OUTPUT:**

Print $$N-1$$ lines where ith line should contain the 'special value' of the graph formed after deleting the edges of first i steps.

**CONTRAINTS:**

1 <= $$N$$ <= 10^{5}

0 <= value of each node <=10^{9}

1 <= $$u$$ , $$v$$ <= $$N$$

1 <= $$x$$ <= $$N-1$$

Explanation

In the 1^{st }first step edge between node number 2 and 3 is deleted so the maximum difference of values is between node number 1 and 2 which is 1.

After deleting edge between node 1 and 2 no two nodes are connected hence answer is 0.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
Bash,
C,
C++,
C++14,
C++17,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
Java 14,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
Python 3.8,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift-4.1,
Swift,
TypeScript,
Visual Basic

Initializing Code Editor...

{"ecfab67": "/pagelets/problems-hint/algorithm/still-maximum/", "117de0c": "/pagelets/show-submission/algorithm/still-maximum/", "ef4cded": "/pagelets/problem-author-tester/algorithm/still-maximum/", "8c90471": "/pagelets/recommended-problems/algorithm/still-maximum/"}