#include<stdio.h>
int n,m,maxbit,v[100010];

void update(int i,int x){
    while(i<=n){
        v[i]+=x;
        i+=(i-(i&i-1));
    }
}

int query(int x){
    int s=0;
    while(x>0){
        s+=v[x];
        x&=(x-1);
    }
    return s;
}

int search(int s){
    int i,poz;
    for(i=0,poz=maxbit;poz;poz>>=1){
        if(i+poz<=n && s>=v[i+poz]){
            i+=poz; s-=v[i];
            if(!s) return i;
        }
    }
    return -1;
}

int main(){
    int i,x,y;
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(maxbit=1;maxbit<=n;maxbit<<=1);
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        update(i,x);
    }
    for(i=1;i<=m;i++){
        scanf("%d",&x);
        switch(x){
            case 0: scanf("%d %d",&x,&y); update(x,y); break;
            case 1: scanf("%d %d",&x,&y); printf("%d\n",query(y)-query(x-1)); break;
            case 2: scanf("%d",&x); printf("%d\n",search(x)); break;
        }
    }
}