Memory Lifetime in a Simplified Garbage Collection Model

You are given an undirected graph with n nodes and m edges, with no self‑loops or multiple edges. The nodes are numbered from 1 to n and represent objects occupying memory. The i-th node occupies a_i units of memory. Each edge represents a bidirectional reference between two objects. The program starts at time 0 with all nodes alive and runs until time q+1. At each second i for i = 1, 2, …, q, one of the following two operations occurs:

• DELETE x y: Delete the edge between node x and node y. It is guaranteed that the same edge is never deleted twice.
• GC: Perform a garbage collection which kills (i.e. deletes) every alive node that is unreachable from node 1. (Note that the deletion of nodes does not remove the edges attached to them.)

After all q operations, at time q+1, the program terminates and all remaining alive nodes are deleted (including node 1). For each node i, let alive_i denote the total time (in seconds) that node i remains alive. (A node that is killed by a GC operation at time t is considered alive during the time interval [0, t), and a node that is never killed by a GC operation remains alive until time q+1.)

Your task is to compute the value of

[ \sum_{i=1}^{n} a_i \times alive_i, ]

where a_i is the memory used by the i-th node.

inputFormat

The first line contains three integers n, m, and q (1 ≤ n, m, q ≤ ...).

The second line contains n integers a₁, a₂, ..., a_n.

The next m lines each contain two integers u and v, indicating an edge between nodes u and v.

The following q lines describe the operations. Each line is either in the format:

• DELETE x y - meaning the edge (x,y) is to be deleted, or
• GC - perform a garbage collection as described above.

outputFormat

Output a single integer, the value of \(\sum_{i=1}^{n} a_i \times alive_i\).

sample

3 2 3
1 2 3
1 2
2 3
GC
DELETE 2 3
GC

21