P5163 WD and the Map.

WD spends all day immersed in maps and cannot pull himself out.

The map that CX asks WD to study can be seen as a directed graph with $n$ nodes and $m$ edges. Since the government is trying to improve people's lives, they will remove some useless roads and use the saved money for economic development. Each city has its own development level $s_i$. For easier management, the government divides the whole map into some regions. Two nodes $u, v$ are in the same region if and only if $u, v$ can reach each other. The government wants to know, at certain times, the sum of the development levels of the top $k$ most developed cities in a region, in order to judge the construction situation. That is, there are three operations in total: `1 a b` means the government removes the edge from $a$ to $b$, and it is guaranteed that this edge exists. `2 a b` means the government invests money to build city $a$, increasing its development level by $b$. `3 a b` means the government wants to know the sum of the development levels of the top $b$ cities (by development level) in the region where city $a$ is located. If there are fewer than $b$ cities in the region, output the sum of the development levels of all cities in that region.

The first line contains three integers $n, m, q$, meaning there are $n$ nodes, $m$ edges, and $q$ queries. The second line contains $n$ positive integers, representing $s_i$, i.e., the development level of each city. The next $m$ lines each contain two integers $u, v$, indicating that initially there is an edge from $u$ to $v$. The next $q$ lines describe the $q$ queries, in the format given in the description.

For each query operation, output one integer, representing the sum of development levels.

$subtask1(19pts):~n\le 100,000,~m\le 200,000,~q\le 200,000$, number of delete operations $\times m\le 1,000,000$. $subtask2(39pts):~n\le 5,000,~m\le 8,000,~q\le 200,000$. $subtask3(42pts):~n\le 100,000,~m\le 200,000,~q\le 200,000$. It is guaranteed that at any time the development level $\le 10^9$. There are no multiple edges (reverse edges are not considered multiple edges) and no self-loops. Translated by ChatGPT 5