Indra is stuck! Surrounded, with no escape from the certain death he will face in the coming moments. His only option - fight for his life! Now, you're probably wondering how he got into this situation...

You see, a few weeks prior Indra was implementing a goblin tree, but the final step befuddled him: how are you meant to burn a sacrificial lamb in the middle of a coding contest? Feeling insulted by Indra's obvious disrespect in skipping the crucial step, the code goblins transported him to the goblin dimension to spend the rest of his days.

The hierarchy of the goblin kingdom in the goblin dimension is like so: There is a king goblin (goblin ~0~), and every goblin who is not the king has a superior. Furthermore, Goblins (as well as Indra) have power ratings. Indra cosplays as a goblin and infiltrates their ranks.

As Indra's fairy godmother, you do not know which goblin he is, but you do worry about him - therefore, you must answer queries of the form "If Indra is goblin ~x~, how many of his direct superiors could he defeat in battle?". First Indra defeats his supervisor, then his supervisor's supervisor, and so on while the sum of their power ratings is less than or equal to his.

Input

The first line contains three integers ~n~, ~q~, and ~p~: the number of goblins, the number of queries, and Indra's power rating.

The next ~n~ lines each contain one integer: the power rating of that goblin (goblins are numbered ~0~ to ~n-1~ in the order given).

The next ~n-1~ lines each contain two integers ~a~ and ~b~, meaning that goblin ~a~ is the superior of goblin ~b~.

Finally, the next ~q~ lines each contain an integer ~a~, representing a query asking what happens if Indra is goblin ~a~.

Output

For each of the ~q~ queries, output a single integer on its own line: the number of goblins above him that he could beat in battle.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le q \le 10^5~
• ~0 \le p \le 10^9~
• Each goblin's power rating is between ~0~ and ~10^9~ (inclusive)
• ~0 \le a, b \le n-1~
• The superiors form a tree rooted at goblin ~0~

Example 1

Input

4 1 10
5
5
5
5
0 1
1 2
2 3
3

Output

2

Explanation

The answer is ~2~: if Indra is goblin ~3~, then he can defeat goblins ~2~ and ~1~.