#include<fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n,op,a,b,m,x;
int v[100010];

int query(int i){
    int nr=0;
    for( ; i!=0 ; i-= (i &- i) )
        nr+=v[i];
    return nr;
}

void actualizare(int i,int a) {
    for ( ; i<=n ; i+= (i &- i))
        v[i]+=a;
    return;
}

int patrascu(int i){ ///cautare cu puteri de 2
    int aux;
    int j,st;
    aux=i;
    j=1;
    while(2*j<=n)
        j*=2;
    st=0;
    while(j!=0){

        if(st+j<=n){
            if(v[st+j]<=i){
                st+=j;
                i-=v[st];
                if(i==0)
                    return st;
            }
        }

        j/=2;
    }

    return -1;
}

int main(){
    fin>>n>>m;
    for(int i=1;i<=n;i++){
        fin>>x;
        actualizare(i,x);
    }
    int i;
    for(int t=1;t<=m;t++){
        fin>>op;
        if(op==0){
            fin>>i>>a;
            actualizare(i,a);
        }
        if(op==1){
            fin>>a>>b;
            fout<<query(b)-query(a-1)<<"\n";
        }
        if(op==2){
            fin>>i;
            fout<<patrascu(i)<<"\n";
        }
    }
    return 0;
}