#include <fstream>
using namespace std;
#define dim 100001

int AIB[dim],n,m;

void update(int Val,int idx){
    while(idx<=n){
        AIB[idx]+=Val;
        idx+=(idx & -idx);
    }
}

int cmf(int idx){
    int sum=0;
    while(idx>0){
        sum+=AIB[idx];
        idx-=(idx & -idx);
    }
    return sum;
}

int query_ab(int a,int b){
    return cmf(b)-cmf(a-1);
}

int find(int cumfre){
    int bitMask=n,idx=0;
    while(bitMask!=0 && idx<n){
        int tIdx=bitMask+idx;
        if(cumfre >= AIB[tIdx]){
            cumfre-=AIB[tIdx];
            idx=tIdx;
            if(!cumfre) return idx;
        }
        bitMask>>=1;
    }
    return -1;
}

int main(){

    ifstream f("aib.in");
    ofstream g("aib.out");

    int x,y,t;
    f >> n >> m;
    for(int i=1;i<=n;i++){
        f >> x;
        update(x,i);
    }
    while(m--){
        f >> t;
        if(t==0){
            f >> x >> y;
            update(y,x);
        }
        else if(t==1){
            f >> x >> y;
            g << query_ab(x,y) << "\n";
        }
        else{
            f >> x;
            g << find(x) <<"\n";
        }
    }
}