#include <bits/stdc++.h>

using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");
int aib[1<<17],n;
int len(int x){
    return x&(-x);
}

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

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


int main()
{
    int i,q,cer,a,b,x,poz,rez;
    in>>n>>q;
    for(i=1;i<=n;++i)
    {
        in>>x;
        update(i,x);
    }
    for(i=1;i<=q;++i){
        in>>cer;
        if(cer==0){
            in>>a>>b;
            update(a,b);
        }
        if(cer==1)
        {
            in>>a>>b;
            out<<querry(b)-querry(a-1)<<'\n';
        }
        if(cer==2){
            in>>x;
            poz=(1<<17);
            rez=0;
            if(x==0){
                out<<-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)
                    out<<rez<<'\n';
                else
                    out<<-1<<'\n';
            }
        }

    }
    return 0;
}