题目背景

WD 整日沉浸在地图中，无法自拔……

题目描述

CX 让 WD 研究的地图可以看做是 $n$ 个点，$m$ 条边的有向图，由于政府正在尝试优化人民生活，他们会废弃一些无用的道路来把省下的钱用于经济建设。

城市都有各自的发达程度 $s_i$。为了方便管理，政府将整个地图划分为一些地区，两个点 $u,v$ 在一个地区当且仅当 $u,v$ 可以互相到达。政府希望知道一些时刻某个地区的前 $k$ 发达城市的发达程度总和，以此推断建设的情况。

也就是说，共有三个操作：

1 a b 表示政府废弃了从 $a$ 连向 $b$ 的边，保证这条边存在。

2 a b 表示政府把钱用于建设城市 $a$，使其发达程度增加 $b$。

3 a b 表示政府希望知道 $a$ 城市所在地区发达程度前 $b$ 大城市的发达程度之和。如果地区中的城市不足 $b$ 个输出该地区所有城市的发达程度总和。

输入格式

第一行两个数 $n,m,q$，表示共 $n$ 个点，$m$ 条边，$q$ 次询问。

第二行 $n$ 个正整数，表示 $s_i$，即每个城市的发达程度。

接下来 $m$ 行每行两个数 $u,v$，表示初始时有一条从 $u$ 连向 $v$ 的边。

接下来 $q$ 行，表示 $q$ 组询问，格式如题目描述。

输出格式

对于每个询问操作，输出一个数，表示发达程度之和。

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

提示

$subtask1(19pts):~n\le 100,000,~m\le 200,000,~q\le 200,000$，删除操作个数$\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$

保证任何时刻发达程度$\le 10^9$，无重边（反向边不算重边）无自环。