#include <bits/stdc++.h>

using namespace std;

int  aib[100001],n;
int len(int x){
    return x-(x&(x-1));
};

int query(int poz){
        int s=0;
        while(poz>0){
            s+=aib[poz];
            poz-=len(poz);
        }
        return s;
};

int update(int poz,int val){
        while(poz<=n){
            aib[poz]+=val;
            poz+=len(poz);
        }
};

int main()
{
    ifstream cin("aib.in");
    ofstream cout("aib.out");
    int m,i,x,poz,a,b,cer,rez;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>x;
        update(i,x);
    }
    for(i=1;i<=m;i++){
        cin>>cer;
        if(cer==0){
            cin>>poz>>x;
            update(poz,x);
        }
        if(cer==1){
            cin>>a>>b;
            cout<<query(b)-query(a-1)<<'\n';
        }
        if(cer==2){
            cin>>x;
            if(x==0){
                cout<<-1<<'\n';
            }
            else{
                rez=0;
                poz=(1<<20);
                while(poz>0){
                    if(rez+poz<=n && aib[rez+poz]<=x){
                        rez+=poz;
                        x-=aib[rez];
                    }
                    poz/=2;
                }
                if(x==0)
                    cout<<rez<<'\n';
                else
                    cout<<-1<<'\n';
            }
        }
    }
    return 0;
}