Problem Description

In programming languages, memory management typically involves the following choices:

• Manual memory management (e.g., C, C++, Rust), which offers high performance but imposes significant programming burdens on the user.
• Using a garbage collection system (e.g., Java, Go), which requires maintaining a runtime system and introduces many unpredictable burdens in terms of memory usage and program performance.

Despite its issues, the most common automated memory management method currently is the Tracing Garbage Collector. The basic idea of this approach is to maintain the reference relationships between objects, forming a graph. During each collection cycle, it scans the reference relationships to deduce objects that are no longer accessible and frees the memory they occupy. The main issue with this traditional approach is the high overhead of maintaining the reference chains, and the cost of scanning increases with more objects to maintain.

Xiao L, a girl who enjoys thinking, finds maintaining a Garbage Collector to be very complex. Therefore, she decides to consider a simpler model (note that it may be completely different from any real-world GC rules!).

Given an undirected graph with $n$ vertices and $m$ edges, without duplicate edges or self-loops, and both vertices and edges numbered starting from 1. Each vertex represents an object that occupies a certain amount of memory, and each edge represents a reference relationship (note that the reference relationship is undirected). The program starts running at time $0$ and ends at time $q + 1$. For each time $i$ from $1$ to $q$, one of the following two operations occurs:

• DELETE $i$, which deletes edge $(x_i, y_i)$, ensuring that no already deleted edge is deleted again.
• GC, which performs a memory collection, i.e., kills all vertices that are not reachable from the starting point and frees the memory they occupy. (Note that deleting a vertex does not delete the edges connected to it.)

You can assume that these operations are executed instantly. After all operations are executed, at time $q + 1$, the program ends and deletes all remaining vertices (including vertex 1).

The memory occupied by vertex $i$ is $a_i$. Now, please calculate $\sum_{i = 1}^{n} a_i \cdot \mathit{alive}_i$, where $\mathit{alive}_i$ represents the duration for which vertex $i$ remains alive. At time $0$, all vertices are alive.

Input Format

The first line of input contains three positive integers $n, m, q$, representing the number of objects, the number of reference relationships, and the number of operations, respectively.

The next $m$ lines each contain two positive integers $x_i, y_i$, representing the two endpoints of the $i$-th reference relationship.

The next $q$ lines each describe an operation that occurs at the $i$-th second and is one of the following two forms:

• The string DELETE followed by a positive integer $x$, as described in the problem statement.
• The string GC, as described in the problem statement.

The last line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the memory size occupied by each object.

Output Format

Output a single integer representing the answer, as described in the problem statement.

Sample Input and Output

Sample Input #1

6 6 8
1 2
2 3
2 4
1 4
2 5
1 6
GC
DELETE 5
DELETE 3
GC
DELETE 1
GC
DELETE 2
GC
1 2 3 4 5 6

Sample Output #1

149

Sample Input #2

See attached file garbage2.in
This set of data satisfies the constraints of test point 6.

Sample Output #2

See attached file garbage2.ans

Sample Input #3

See attached file garbage3.in
This set of data satisfies the constraints of test point 11.

Sample Output #3

See attached file garbage3.ans

Notes/Hints

Sample 1 Explanation

At the $4$th second, vertex $5$ is deleted.

At the $6$th second, vertices $2$ and $3$ are deleted.

At the $9$th second, vertices $1$, $4$, and $6$ are deleted.

The answer is $5 \times 4 + (2 + 3) \times 6 + (1 + 4 + 6) \times 9 = 20 + 30 + 99 = 149$.

Data Size and Constraints

For all data, $1 \leq n, m, q \leq 4 \times 10^5$, $1 \leq a_i \leq 10^8$.

Specific data sizes and constraints are as follows:

见题面 Input 部分

见题面 Output 部分