#include <fstream>
using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int n,m,a,b,i,j,v[100001];

int caut(int k){
    int p;
    for(p=1;p*2<=n;p*=2);
    int st;

    for(st=0; p; p/=2){
        if(st+p<=n){
            if(v[st+p]<=k){
                st+=p;
                k-=v[st];
            }
            if(k==0 && st)
                return st;
        }
    }

    return -1;
}

void upd(int x, int p){
    for(;p<=n;p+=(p&-p))
        v[p]+=x;
}

int query(int p){
    int sol=0;
    for(;p;p-=(p&-p))
        sol+=v[p];

    return sol;
}

int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>j;
        upd(j,i);
    }

    for(i=1;i<=m;i++){
        fin>>j;

        if(j==0){
            fin>>a>>b;
            upd(b,a);
            continue;
        }
        if(j==1){
            fin>>a>>b;
            fout<<query(b)-query(a-1)<<"\n";
            continue;
        }

        fin>>a;
        fout<<caut(a)<<"\n";
    }

    return 0;
}