#include <fstream>
#include <vector>
using std::vector;

void add(vector<unsigned> &tree, unsigned idx, unsigned val){
    while(idx<=tree.size()){
        tree[idx]+=val;
        idx+= idx & (-idx);
    }
}
unsigned getcumulative(const vector<unsigned> &tree, unsigned idx){
    unsigned sum=0;
    while(idx>0){
        sum+=tree[idx];
        idx -= idx & (-idx);
    }
    return sum;
}
bool findSm(const vector<unsigned> &tree, unsigned cumfreq, unsigned *result){
    unsigned bitmask=1,temp=tree.size()>>1;
    while(temp>0){ bitmask<<=1; temp>>=1; }

    unsigned idx=0;
    while( (bitmask!=0) && (temp<=tree.size()) ){
        temp=idx+bitmask;
        if(cumfreq>=tree[temp]){
            idx=temp;
            cumfreq-=tree[idx];
        }
        bitmask>>=1;
    }
    if(cumfreq==0){
        *result=idx;
        return true;
    }
    else return false;
}

int main(){
    std::ifstream fin("aib.in");
    std::ofstream fout("aib.out");

    unsigned N,M;
    fin>>N>>M;
    vector<unsigned> tree(N+1,0);

    for(unsigned i=1;i<=N;++i){
        unsigned x; fin>>x;
        add(tree,i,x);
    }

    unsigned temp1,temp2;
    char c;
    while(M--){
        fin>>c>>temp1;
        switch(c){
            case '0':
                fin>>temp2;
                add(tree,temp1,temp2);
                break;
            case '1':
                fin>>temp2;
                fout<<getcumulative(tree,temp2)-getcumulative(tree,temp1-1)<<'\n';
                break;
            case '2':
                if(temp1!=0&&findSm(tree,temp1,&temp2))
                    fout<<temp2<<'\n';
                else fout<<"-1\n";
                break;
        }
    }
}