Background

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

Problem Description

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.

Input Format

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.

Output Format

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

5 8 8
4 2 1 1 3
2 5
4 2
5 3
1 3
4 5
5 1
1 5
1 4
3 3 1
1 4 5
3 3 3
3 4 1
3 1 5
3 2 4
1 5 3
2 3 4

1
1
4
10
10

Hint

$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