8-3

In Chotu's World, there were N towns along with M bidirectional roads connecting them. With time, some roads became unusable, and nobody repaired them.

As Chotu is fond of his world's history, he now wants to undertake a small research study. For this purpose, he wants to write a program capable of processing a query which takes an integer K as input which means that the road numbered K in the input becomes unusable road.

Let's call a subset of towns a region if it is possible to get from each town in the subset to every other town in the subset by the usable (those, which haven't already been destroyed) roads, possibly, via some intermediary cities of this subset. The population of the region is, then, the sum of populations of all the towns in the region.

You are given the initial road system, the initial population in each town and Q queries, each being of type explained above. Your task is to maintain the size of the most populated region after each query.

Input

The first line of each test case contains three space-separated integers — N, M, and Q — denoting the number of cities, the number of roads, and the number of queries, respectively.

The following line contains N space-separated integers, the i^th of which denotes the initial population of the i^th city.

The j^th of the following M lines contains a pair of space-separated integers — Xj, Yj — denoting that there is a bidirectional road connecting the cities numbered Xj and Yj.

Each of the following Q lines contains integer K as described above.

Output

Output Q lines. On the i^th line, output the size of the most populated region after performing i queries.

Constraints

1 ≤ N, M, Q ≤ 5 * 10^5 
1 ≤ Xj, Yj ≤ N 
Roads numbers are based in 1-indexed.
There is no road that gets removed twice or more.
1 ≤ population of city ≤ 10^9

Note : Use scanf / printf to avoid TLE

SAMPLE INPUT
3 3 3
1 2 3
1 2
2 3
3 1
1
2
3

SAMPLE OUTPUT
6
4
3

Source: hackerearth | Difficulty: HARD


Solutions: