In typical scenarios, programming languages make the following choices when managing memory:

• Allowing users to perform manual memory management (C, C++, Rust, etc.), which yields excellent performance but places a significant programming burden on the user.
• Using a garbage collection system (Java, Go, etc.), which requires maintaining a runtime system and introduces many unpredictable burdens regarding memory usage and program performance.

Despite these issues, the most common method for automated memory management remains Tracing Garbage Collection. The fundamental idea of this approach is to maintain the reference relationships between objects to form a graph. During each collection, it scans the reference relationships to deduce objects that can no longer be accessed and releases the memory they occupy. The biggest problem with this traditional approach is that maintaining the reference chain incurs significant overhead, and as the number of objects being maintained increases, the cost of scanning also increases.

Little L is a girl who likes to think. She found that maintaining a Garbage Collector is a very complex task, so she decided to consider a simpler model (note that it may be completely different from any real-world GC rules!).

For an undirected graph with $n$ nodes and $m$ edges, with no multiple edges or self-loops, nodes and edges are labeled starting from 1. Each node represents an object occupying a certain amount of memory, and each edge corresponds to a reference relationship (note that this reference relationship is undirected). The program starts running at time 0 and ends at time $q + 1$. For each time $i = 1, 2, 3, \dots, q$, the program performs one of the following two operations:

• DELETE i: Delete edge $(x_i, y_i)$. It is guaranteed that an already deleted edge will not be deleted again.
• GC: Perform a memory collection, i.e., kill all nodes that cannot be reached from node 1 and release the memory they occupy. (Note that deleting nodes here does not delete the edges connected to these nodes.)

You can assume that these operations are executed instantaneously. After all operations are performed, i.e., at time $q + 1$, the program ends, and all remaining nodes (including node 1) are deleted.

The memory occupied by the $i$-th node is $a_i$. Now, please calculate the total cost of the program, which is $\sum_{i=1}^n a_i \cdot t_i$, where $t_i$ represents the time the $i$-th node survives. At time 0, all nodes are alive.

Input

The first line 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 contain one of the following two forms, where the $i$-th line represents the operation performed at time $i$:

• A string DELETE and a positive integer $x$, with the meaning described in the problem statement.
• A string GC, with the meaning described in the problem statement.

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

Output

Output a single integer representing the cost of the program, as described in the problem statement.

Examples

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

Output 1

149

Note 1

At time 4, node 5 is deleted. At time 6, nodes 2 and 3 are deleted. At time 9, nodes 1, 4, and 6 are deleted. Therefore, the program's cost is $5 \times 4 + (2 + 3) \times 6 + (1 + 4 + 6) \times 9 = 20 + 30 + 99 = 149$.

Input 2

(input data for Example 2)

Output 2

(output data for Example 2)

Note 2

This test case satisfies the constraints of test case 6.

Input 3

(input data for Example 3)

Output 3

(output data for Example 3)

Note 3

This test case satisfies the constraints of test case 11.

Constraints

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

The specific data scale and constraints are shown in the table below.