Problem Brief

The Crazy Ruler

You are provided with a map representing a connected country consisting of N cities. The cities are numbered from 1 to N and they are interconnected by N-1 edges, forming a tree-like structure.

Each city's population possesses a unique measurement denoting their satisfaction level, represented by an array of length N. The satisfaction level of the city number i is given by the value A[i].

This country is governed by a peculiar king who takes a keen interest in conducting intriguing mathematical evaluations which sometimes appear nonsensical to assess the country's condition. His evaluation method is as follows:

He calculates the sum of the satisfaction levels of the cities, which he denotes as the satisfaction level. In other words, he calculates the sum of the unique satisfaction level of the number of cities.

Aware of numerous conflicts and political issues, the king recognizes the necessity of dividing his country into precisely two parts by removing a single edge. His objective is to identify the optimal edge that, when removed, would split the country into two parts, maximizing the sum of the king's evaluation for the two resulting countries.

Find the maximum possible sum of satisfaction levels, representing the combined evaluations for the two resulting countries. Since the answer can be very large, return it modulo 10^9+7.

Input Format

The first line contains an integer, N, denoting the number of cities in the country.
The next line contains N integers, M, denoting the number of edges in the country.
The next line contains an integer, M, denoting the number of cities in the country.
Each line of the subsequent lines (where 0 ≤ i < M) contains two integers, U and V, denoting the two cities that an edge connects.
Each line of the N subsequent lines (where 0 ≤ i < N) contains an integer describing A[i].

1Example 1

Input

A = [1, 2, 3, 4, 5], edges = [[1, 2], [1, 3], [3, 4], [3, 5]]

Output

Explanation

For satisfaction levels, edge_removed=[(1,2), (1,3), (3,4), (3,5)], we get satisfaction=[(14,1), (12,3), (11,4), (11,4)].

In this case, the optimal solution is to cut the edge (1,3), which separates the tree into two trees [1,2] and [3,4,5]. The resulting trees have satisfaction levels of 3 and 12, respectively. Therefore, the best answer to evaluate is 3 + 12 = 15.

Hence, the answer is 15.

2Example 2

Input

A = [1, 2, 2, 2, 2], edges = [[1, 2], [1, 3], [3, 4], [3, 5]]

Output

Explanation

For each edge cut of the tree to obtain "5 + 5 = 10" as the best answer.

Hence, the answer is 10.

3Example 3

Input

A = [1, 2, 3, 1, 1, 1, 1], edges = [[1, 2], [1, 3], [1, 4], [3, 5], [3, 6], [4, 7]]

Output

Explanation

For each edge cut of the tree to obtain "6 + 3 = 9" as the best answer.

In this case, the optimal solution is to cut the edge (1,3), which separates the tree into two trees [1,2,4,7] and [3,5,6]. The resulting trees have satisfaction levels of 6 and 3, respectively. Therefore, the best answer to evaluate is 6 + 3 = 9.

Hence, the answer is 9.

Constraints

Limits and guarantees your solution can rely on.

1 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
1 ≤ U, V ≤ N
1 ≤ A[i] ≤ 10^9