#include <stdio.h>
#include <stdlib.h>
int aib[100001],v[100001],n;
void upd(int pl,int i){
    while(i<=n){
        aib[i]+=pl;
        i+=i&(i-1)^i;
    }
}
int sum(int a){
    int s=0;
    while(a>0){
        s+=aib[a];
        a=a-(a&(a-1))^a;
    }
    return s;
}
int caut(int s){
    int p,i;
    for(p=1;p<n;p*=2);
    for(i=0;p>0;p/=2)
        if(i+p<=n && sum(i+p)<=s)
            i+=p;
    return i;
}
int main()
{
    FILE*fin,*fout;
    int k,i,m,c,a,b;
    fin=fopen("aib.in","r");
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d",&v[i]);
        upd(v[i],i);
    }
    fout=fopen("aib.out","w");
    for(i=0;i<m;i++){
        fscanf(fin,"%d",&c);
        if(c==2){
            fscanf(fin,"%d",&a);
            if(sum(caut(a))==a)
                fprintf(fout,"%d\n",caut(a));
            else
                fprintf(fout,"-1\n");
        }
        if(c==0){
            fscanf(fin,"%d%d",&a,&b);
            upd(b,a);
        }
        if(c==1){
            fscanf(fin,"%d%d",&a,&b);
            fprintf(fout,"%d\n",sum(b)-sum(a-1));
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}