Subtree Sum Queries in a Tree

You are given a tree with N nodes, rooted at node 1. Each node i has an associated value val[i]. Your task is to answer Q queries. For each query, you are given a node u and you must compute the sum of values of all nodes in the subtree of u (including u itself). In mathematical terms, if subtree(u) denotes the set of nodes in the subtree of u, you need to compute: \[ answer = \sum_{x \in subtree(u)} val[x] \]

The tree is provided as an undirected connected graph with N - 1 edges. It is guaranteed that the tree is rooted at node 1.

inputFormat

The input is given from standard input (stdin) in the following format:

N
val[1] val[2] ... val[N]
u1 v1
u2 v2
... (N - 1 lines of edges)
Q
query1
query2
... (Q lines, each containing a node number)

Here, N is the number of nodes. The second line contains N integers where the i-th integer represents the value of node i. Each of the following N-1 lines contains two integers u and v indicating there is an edge between nodes u and v. After the edges, an integer Q follows, representing the number of queries. Each of the next Q lines contains one query which is a node number.

outputFormat

For each query, print on a new line the sum of values of all nodes in the subtree of the queried node.

## sample

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

15
11
3

</p>