#include<iostream>
using namespace std;

#define NMAX 100001

int n,aib[NMAX];
void update(int idx,int val){
    for(;idx<=n;idx+=(idx&-idx)){
        aib[idx]+=val;
    }
}
long long query(int idx){
    long long sum=0;
    for(;idx>0;idx-=(idx&-idx)){
        sum+=aib[idx];
    }
    return sum;
}
signed main(){
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif // LOCAL
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        update(i,x);
    }
    for(;q;--q){
        int op;
        cin>>op;
        if(!op){
            // update
            int i,x;
            cin>>i>>x;
            update(i,x);
            continue;
        }
        if(op==1){
            // query a-b
            int a,b;
            cin>>a>>b;
            if(a>b)swap(a,b);
            cout<<query(b)-query(a-1)<<"\n";
            continue;
        }
        // query dinalalalt
        int k;
        cin>>k;
        int st=1,dr=n,ans=-1;
        while(st<=dr){
            int mij=(st+dr)/2;
            auto q=query(mij);
            if(k<=q){
                if(k==q)ans=mij;
                dr=mij-1;
            }else{
                st=mij+1;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}