ADASALES - Ada and Travelling Salesman

Ada the Ladybug lives in Bugladesh. It is a very specific country - there are plenty of cities, but since the government doesn't "waste" money, there is only one simple path between each pair of cities.

Ada is working as Traveling Salesman. She travels between cities, buying and selling products. A product has fixed price in each city (same for buy/sale). Since Ada travels with bike (to avoid payments for travels) so she can carry at most one item at a moment.

She is currently in some city, and she wants to choose such city, that she will make as much money as possible by travelling to that city (by simple path). Can you help her?

Input

The first line will contain 0 < N ≤ 105, 0 < Q ≤ 5*105, number of cities and number of queries respectively.

Then one line with N integers follow, 1 ≤ Ai ≤ 109, the price in ith city.

Afterward N-1 lines follow, each containing two numbers 0 ≤ i,j < N (i ≠ j), meaning that there is a simple path between city i and city j.

Then Q lines follows, each containing exactly one integer 0 ≤ i < N- the city in which Ada begins.

Output

Print Q lines, the maximal amount of money, Ada can earn.

Example Input

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

Example Output

4
3
3
1
1
2

Example Input

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

Example Output

6
3

Output explanations [Possible destination cities of first example input]

4
4
4
2
2
2

Note that some of the destinations might have ended somewhere else, but it would result in same income!


Added by:Morass
Date:2017-02-12
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2018-03-01 07:09:09
Cant understand the question. Can you provide more details for explanation of example. What are the constraints?

When there is only one way to reach a city and path is available, wouldn't a salesman just go to the highest price or if she has to purchase from the origin city then wouldn't we just calculate the modulus of difference in the price.
2018-02-15 07:00:28
to easy for rtz
2017-02-23 01:29:46
@[Rampage] Blue.Mary: Thank you so much for pointing out. I repaired it so I hope it is all-OK now ^_^ Have nice day!!
2017-02-23 01:21:07 [Rampage] Blue.Mary
(1) The meaning of Ai is not specified in the input section.
(2) There's an extra "6" after the end of the example input 1.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.