def xx(x,y):
    return x+y

def aa(seg,m,vv):
    while m>1:
        m//=2
        seg[m]=vv(seg[m*2],seg[m*2+1])
def bb(seg,l,r,res,vv):
    while l<r:
        if l&1:
            res=vv(res,seg[l]);l+=1
        if r&1:
            r-=1;res=vv(res,seg[r])
        l//=2;r//=2
    return res

n,q=map(int,input().split())
v=1<<n.bit_length()
seg1=[0]*v*2
seg2=[-1]*v*2
seg3=[1<<30]*v*2
a=list(map(int,input().split()))
for i in range(n):
    seg1[i+v]=a[i];aa(seg1,i+v,xx)
    seg2[i+v]=i;aa(seg2,i+v,max)
    seg3[i+v]=i;aa(seg3,i+v,min)
for i in range(q):
    a,b=map(int,input().split());b-=1
    if a==1:
        if seg2[b+v]!=-1:
            seg2[b+v]=-1;aa(seg2,b+v,max)
            seg3[b+v]=1<<39;aa(seg3,b+v,min)
    elif a==2:
        if seg2[b+v]==-1:
            seg2[b+v]=b;aa(seg2,b+v,max)
            seg3[b+v]=b;aa(seg3,b+v,min)
    elif a==3:
        seg1[b+v]+=1;aa(seg1,b+v,xx)
    else:
        print(bb(seg1,v+bb(seg2,v,b+v,-1,max)+1,v+bb(seg3,b+v,v*2,1<<30,min)+1,0,xx))