#include <bits/stdc++.h>

int aib[1<<18];

void update(int val,int nod,int st,int dr,int p){
    if(st==dr)
        aib[p]+=val;
    else {
        int mij=(st+dr)/2;
        if(nod<=mij)
            update(val,nod,st,mij,p*2);
        else update(val,nod,mij+1,dr,p*2+1);
        aib[p]=aib[p*2]+aib[p*2+1];
    }
}

int calc(int a,int b,int st,int dr,int p){
    if(a<=st && dr<=b)
        return aib[p];
    else {
        int mij=(st+dr)/2,s=0;
        if(a<=mij){
            s+=calc(a,b,st,mij,p*2);
        }
        if(b>=mij+1)
        {
            s+=calc(a,b,mij+1,dr,p*2+1);
        }
        return s;
    }
}

int main()
{
    int n,m,k,i,q,a,b,r,p,s;
    FILE*fi,*fo;
    fi=fopen("aib.in","r");
    fo=fopen("aib.out","w");
    fscanf(fi,"%d%d",&n,&m);
    for(i=1;i<=n;i++){
        fscanf(fi,"%d",&k);
        update(k,i,1,n,1);
    }
    for(i=0;i<m;i++){
        fscanf(fi,"%d",&q);
        if(q==0)
        {
            fscanf(fi,"%d%d",&a,&b);
            update(b,a,1,n,1);
        }
        else if(q==1){
            fscanf(fi,"%d%d",&a,&b);
            fprintf(fo,"%d\n",calc(a,b,1,n,1));
        }
        else if(q==2){
            fscanf(fi,"%d",&k);
            r=0;
            p=1<<17;
            s=0;
            q=0;
            while(p>0){
                if(r+p<=n){
                    q=calc(r+1,r+p,1,n,1);
                    if(s+q<k){
                    r+=p;
                    s+=q;
                    }
                }
                p/=2;
            }
            if(s+calc(r+1,r+1,1,n,1)==k)
                fprintf(fo,"%d\n",r+1);
            else fprintf(fo,"-1\n");
        }
    }
    fclose(fi);
    fclose(fo);
    return 0;
}