A. Ancient Berland Roads
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In Ancient Berland, there were $$$N$$$ towns, along with $$$M$$$ bidirectional roads connecting them. With time, some roads became unusable, and nobody repaired them.

As a person who is fond of Ancient Berland history, you now want to undertake a small research study. For this purpose, you want to write a program capable of processing the following kinds of queries:

  • D j: meaning that the $$$j$$$th road in the input became unusable. The road numbers are $$$1$$$-indexed.
  • P i z: meaning that the population of the $$$i$$$th town became $$$z$$$.

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 roads, either directly or indirectly. The population of the region is 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 one of two types above. Your task is to report 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$$$ ($$$1 \le N, Q \le 500,000$$$, $$$0 \le M \le 500,000$$$), denoting the number of cities, the number of roads, and the number of queries, respectively.

The following line contains $$$N$$$ space-separated integers $$$P_1, \ldots, P_N$$$ ($$$1 \le P_i \le 100,000$$$), where $$$P_i$$$ denotes the initial population of the $$$i$$$th city.

The $$$j$$$th of the following $$$M$$$ lines contains a pair of space-separated integers $$$X_j$$$ and $$$Y_j$$$ ($$$1 \le X_j \lt Y_j \le N$$$), denoting that there is a bidirectional road connecting the cities numbered $$$X_j$$$ and $$$Y_j$$$. The roads are unique, that is, no two roads connect the same pair of towns.

Each of the following $$$Q$$$ lines describes a query in one of the forms described earlier. No road becomes unusable twice, and no town's population ever exceeds $$$100,000$$$.

Output

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

Example
Input
3 3 6
1 2 3
1 2
2 3
1 3
P 1 3
D 1
P 2 3
D 2
P 3 10
D 3
Output
8
8
9
6
13
10
Note

In the sample:

  • After the first query, the populations are (3, 2, 3) and the most populated region is {1, 2, 3}.
  • After the second query the populations and the regions remain the same.
  • After the third query the populations are (3, 3, 3) and the most populated region is again {1, 2, 3}.
  • After the fourth query the populations remain the same, but we have two regions: {1, 3} and {2}. The most populated region is {1, 3}.
  • After the fifth query the populations become equal to (3, 3, 10) respectively, and the most populated region is again {1, 3}.
  • After the last query we have populations the same, but now every city forms it own separate region, and the most populated region is region {3}.