Dynamic Regional Development Query

You are given a directed graph with \( n \) nodes and \( m \) edges. Each node (city) has an initial development degree \( s_i \). The government performs three types of operations:

• 1 a b: Remove the edge from node \( a \) to node \( b \). It is guaranteed that this edge exists.
• 2 a b: Increase the development degree of city \( a \) by \( b \), i.e. set \( s_a = s_a + b \).
• 3 a b: For the (strongly connected) region containing city \( a \) (i.e. the set of nodes that are mutually reachable), calculate the sum of the top \( k \) (where \( k = b \)) highest development degrees. If the region contains less than \( k \) cities, output the sum of all development degrees in that region.

The input begins with three integers \( n \), \( m \), and \( q \). The second line contains \( n \) integers \( s_1, s_2, \dots, s_n \). Each of the following \( m \) lines contains two integers representing a directed edge from \( a \) to \( b \). Finally, there are \( q \) operations as described above. For every operation of type 3, output the answer on a new line.

Note: Use LaTeX formatting for formulas (e.g. \( n \), \( m \), \( s_i \) etc.)

inputFormat

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

The second line contains \( n \) integers representing \( s_1, s_2, \dots, s_n \), the development degrees of the cities.

The next \( m \) lines each contain two integers \( a \) and \( b \) representing a directed edge from \( a \) to \( b \).

The following \( q \) lines each contain an operation in one of the following formats:

• 1 a b
• 2 a b
• 3 a b

outputFormat

For each operation of type 3, output a single integer which is the sum of the top \( k \) (or all, if there are fewer than \( k \)) highest development degrees in the region containing city \( a \). Each output should be on a separate line.

sample

4 4 5
10 20 30 40
1 2
2 3
3 1
4 3
3 1 2
2 4 5
3 4 3
1 2 3
3 1 2

50
45
30