# include <fstream>
# define DIM 100010
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int v[DIM],n,m,i,x,p,k,st,dr,mij,val,a,b,h;
void update(int a,int b){
    int i;
    for(i=a;i<=n;i+=(i&(-i)))
        v[i]+=b;
}
int sum(int p){
    int i,s=0;
    for(i=p;i>=1;i-=(i&(-i)))
        s+=v[i];
    return s;
}
int main () {
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>x;
        update(i,x);
    }
    for(i=1;i<=m;i++){
        fin>>val;
        if(val==0){
            fin>>a>>b;
            update(a,b);
        }
        if(val==1){
            fin>>a>>b;
            fout<<sum(b)-sum(a-1)<<"\n";
        }
        if(val==2){
            fin>>k;
            st=1;
            dr=n;
            while(st<=dr){
                mij=(st+dr)/2;
                h=sum(mij);
                if(h>=k)
                    dr=mij-1;
                else
                    st=mij+1;
            }
            if(sum(st)==k)
                fout<<st<<"\n";
            else
                fout<<-1<<"\n";
        }
    }
    return 0;
}