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

void add(vector<unsigned> &tree, unsigned idx, unsigned val){
    while(idx<=tree.size()-1){
        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;
}
unsigned findSm(const vector<unsigned> &tree, unsigned cumfreq){
    unsigned bitmask=1,temp=(tree.size()-1)>>1;
    while(temp>0){ bitmask<<=1; temp>>=1; }

    unsigned idx=0;
    for(;bitmask;bitmask>>=1){
        if((bitmask+idx)<tree.size() && cumfreq>=tree[bitmask+idx]){
            idx+=bitmask;
            cumfreq-=tree[idx];
            if(cumfreq==0) return idx;
        }
    }
    if(cumfreq==0) return idx;
    else return 0;
}

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) fout<<"-1\n";
                else{
                    temp2=findSm(tree,temp1);
                    if(temp2==0) fout<<"-1\n";
                    else fout<<temp2<<'\n';
                }
                break;
        }
    }
}