#include<fstream>
using namespace std;
int aib[100005],n,m,tip,x,a,b;
ifstream in("aib.in"); ofstream out("aib.out");
void update(int val, int poz){
    for(int i=poz; i<=n; i+=(i&(-i)))
        aib[i]+=val;
}
int sum(int poz){
    int rez=0;
    for(int i=poz;i>0;i-=i&(-i))
        rez+=aib[i];
    return rez;
}
int query(int a){
    int st=1,dr=n;
    int mij,acm;
    while(st<=dr){
        mij=(st+dr)/2;
        acm=sum(mij);
        if(acm==a){ return mij;}
        if(acm>a){dr=mij-1;}
        else st=mij+1;
    }
    return -1;
}
int main(){
    in>>n>>m;
    for(int i=1;i<=n;++i){
        in>>x;
        update(x,i);
    }
    for(int i=1;i<=m;++i){
        in>>tip;
        switch(tip){
            case 0:{
                in>>a>>b;
                update(b,a);
                break;
            }
            case 1:{
                in>>a>>b;
                if(a>b) a^=b^=a^=b;
                out<<sum(b)-sum(a-1)<<'\n';
                break;
            }
            case 2:{
                in>>a;
                out<<query(a)<<'\n';
                break;
            }
        }
    }
}
/*
Arbori de intervale:
In fiecare elem din vectorul aib este suma pe intervalul i-2^k+1,i, unde k este numarul de 0uri terminale din
reprezentarea binara a lui i
*/