首先将操作倒序，把删边转化为加边。先考虑若边是无向边，条件为连通，要怎么处理。
可以用并查集来维护连通性，对每个连通块维护一颗权值线段树，连通块的合并用线段树合并来实现，线段树同时也支持了修改点权。
然后再考虑对于有向边和强连通分量要怎么做。无向边的作用是使两个连通块成为一个连通块，有向边的作用是使两个强连通分量成为一个强连通分量。但是加入一条有向边后，其两端的强连通分量不一定合并为一个强连通分量，随着其他边的加入，该边才有可能发挥其作用。
因此可以考虑对每条边二分出一个时刻，为加入该边后，随着边的加入，其两端强连通分量合并的最早时刻。单独考虑每条边不现实，采取整体二分来处理。对于当前二分的时间区间([l,r])，对于时间在([0,mid])的所有边都加入，然后用(tarjan)来缩点，若满足条件就寻找更早的答案，不满足就尝试晚一些的答案。
发现在二分过程中每次都加入([0,mid])的所有边来进行缩点，复杂度无法接受。对于当前的情况，可以利用之前二分得到的缩点结果，通过并查集来维护每个点所在的强连通分量，连边直接在强连通分量之间连边即可。对于二分的区间([l,r])，已经连好了区间([0,mid])的边，递归时先进入区间([mid+1,r])，这样就能利用上之前的连边情况，递归进入区间([l,mid])之前，需要清除之前连边的影响，这里用可撤销并查集实现即可。
二分出时刻后，类比无向图的处理就行了。
(code:)
#include<bits/stdc++.h>
#define maxn 800010
#define maxm 10000010
#define mid ((l+r)>>1)
#define mk make_pair
#define ask(x) (lower_bound(s+1,s+tot+1,x)-s)
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,qu,top,tot,cnt,dfn_cnt,s_top,tree_cnt;
int size[maxn],fa[maxn],t[maxn],dfn[maxn],low[maxn],sta[maxn];
int ls[maxm],rs[maxm],rt[maxn],siz[maxm];
ll a[maxn],s[maxn],sum[maxm],ans[maxn];
bool vis[maxn];
map<pair<int,int>,int> mp;
struct edge
{
int to,nxt;
}e[maxn];
int head[maxn],edge_cnt;
void add(int from,int to)
{
e[++edge_cnt]=(edge){to,head[from]};
head[from]=edge_cnt;
}
struct node
{
int x,y,t,opt;
}p[maxn],p1[maxn],p2[maxn],q[maxn];
bool cmp(const node &a,const node &b)
{
if(a.t==b.t) return a.opt<b.opt;
return a.t<b.t;
}
struct Stack
{
int x,y;
}st[maxn];
int find(int x)
{
return fa[x]==x?x:find(fa[x]);
}
void merge(int x,int y)
{
x=find(x),y=find(y);
if(x==y) return;
if(size[x]<size[y]) swap(x,y);
st[++top]=(Stack){x,y},size[x]+=size[y],fa[y]=x;
}
void del(int id)
{
int x=st[id].x,y=st[id].y;
fa[y]=y,size[x]-=size[y];
}
void tarjan(int x)
{
dfn[x]=low[x]=++dfn_cnt,sta[++s_top]=x,vis[x]=true;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
int p=sta[s_top--],now;
vis[p]=false;
if(p==x) return;
do
{
now=sta[s_top--],vis[now]=false,merge(p,now);
}while(now!=x);
}
}
void clear(int n)
{
edge_cnt=dfn_cnt=0;
for(int i=1;i<=n;++i) head[t[i]]=dfn[t[i]]=low[t[i]]=0;
}
void solve(int L,int R,int l,int r)
{
if(L>R) return;
if(l==r)
{
for(int i=L;i<=R;++i) p[i].t=l;
return;
}
int now=top,num=0,cnt1=0,cnt2=0;
for(int i=L;i<=R;++i)
{
if(p[i].t>mid) continue;
int x=find(p[i].x),y=find(p[i].y);
t[++num]=x,t[++num]=y,add(x,y);
}
for(int i=1;i<=num;++i)
if(!dfn[t[i]])
tarjan(t[i]);
for(int i=L;i<=R;++i)
{
if(p[i].t<=mid&&find(p[i].x)==find(p[i].y)) p1[++cnt1]=p[i];
else p2[++cnt2]=p[i];
}
for(int i=1;i<=cnt1;++i) p[L+i-1]=p1[i];
for(int i=1;i<=cnt2;++i) p[L+cnt1+i-1]=p2[i];
clear(num),solve(L+cnt1,R,mid+1,r);
while(top>now) del(top--);
solve(L,L+cnt1-1,l,mid);
}
void modify(int l,int r,int pos,int v,int &cur)
{
if(!cur) cur=++tree_cnt;
siz[cur]+=v,sum[cur]+=s[pos]*v;
if(l==r) return;
if(pos<=mid) modify(l,mid,pos,v,ls[cur]);
else modify(mid+1,r,pos,v,rs[cur]);
}
ll query(int l,int r,int k,int cur)
{
if(k>siz[cur]) return sum[cur];
if(l==r) return s[l]*k;
if(k<=siz[rs[cur]]) return query(mid+1,r,k,rs[cur]);
return query(l,mid,k-siz[rs[cur]],ls[cur])+sum[rs[cur]];
}
int merge(int x,int y,int l,int r)
{
if(!x||!y) return x+y;
if(l==r)
{
siz[x]+=siz[y],sum[x]+=sum[y];
return x;
}
ls[x]=merge(ls[x],ls[y],l,mid),rs[x]=merge(rs[x],rs[y],mid+1,r);
siz[x]=siz[ls[x]]+siz[rs[x]],sum[x]=sum[ls[x]]+sum[rs[x]];
return x;
}
int main()
{
read(n),read(m),read(qu),cnt=m;
for(int i=1;i<=n;++i)
read(a[i]),s[++tot]=a[i],fa[i]=i,size[i]=1;
for(int i=1;i<=m;++i)
read(p[i].x),read(p[i].y),mp[mk(p[i].x,p[i].y)]=i;
for(int i=1;i<=qu;++i)
{
read(q[i].opt),read(q[i].x),read(q[i].y),q[i].t=qu-i+1;
if(q[i].opt==1) p[mp[mk(q[i].x,q[i].y)]].t=q[i].t;
if(q[i].opt==2) a[q[i].x]+=q[i].y,s[++tot]=a[q[i].x];
}
sort(s+1,s+tot+1),tot=unique(s+1,s+tot+1)-s-1,solve(1,m,0,qu+1);
for(int i=1;i<=n;++i)
modify(1,tot,ask(a[i]),1,rt[i]),fa[i]=i,size[i]=1;
for(int i=1;i<=qu;++i)
if(q[i].opt!=1)
p[++cnt]=q[i];
sort(p+1,p+cnt+1,cmp);
for(int i=1;i<=cnt;++i)
{
int x=p[i].x,y=p[i].y,t=p[i].t,opt=p[i].opt,f;
if(!opt)
{
x=find(x),y=find(y);
if(x==y) continue;
if(size[x]<size[y]) swap(x,y);
size[x]+=size[y],fa[y]=x;
rt[x]=merge(rt[x],rt[y],1,tot);
}
if(opt==2)
{
f=find(x),modify(1,tot,ask(a[x]),-1,rt[f]);
a[x]-=y,modify(1,tot,ask(a[x]),1,rt[f]);
}
if(opt==3) f=find(x),ans[qu-t+1]=query(1,tot,y,rt[f]);
}
for(int i=1;i<=qu;++i)
if(q[i].opt==3)
printf("%lld
",ans[i]);
return 0;
}