#include<stdio.h>
#define N 150000
int v[N+1],n;
void update(int poz,int val){
    while(poz<=n){
        v[poz]+=val;
        poz+=(poz&-poz);
    }
}
int sum(int poz){
    int s=0;
    while(poz){
        s+=v[poz];
        poz&=poz-1;
    }
    return s;
}
int cauta(int poz){
    int st=1,dr=n;
    while(st<=dr){
        int mij=(st+dr)/2;
        if(sum(mij)==poz)
            return mij;
        if(sum(mij)<poz)
            st=mij+1;
        else
            dr=mij-1;
    }
    return -1;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("aib.in","r");
    fout=fopen("aib.out","w");
    int m;
    fscanf(fin,"%d%d",&n,&m);
    int i;
    for(i=1;i<=n;i++){
        int x;
        fscanf(fin,"%d",&x);
        update(i,x);
    }
    for(i=0;i<m;i++){
        int op;
        fscanf(fin,"%d",&op);
        if(op==0){
            int a,b;
            fscanf(fin,"%d%d",&a,&b);
            update(a,b);
        }
        else
            if(op==1){
                int a,b;
                fscanf(fin,"%d%d",&a,&b);
                fprintf(fout,"%d\n",sum(b)-sum(a-1));
            }
        else{
            if(op==2){
                int k;
                fscanf(fin,"%d",&k);
                fprintf(fout,"%d\n",cauta(k));
            }
        }
    }
    return 0;
}