#include <fstream>


using namespace std;
#define int long long
int n,v[100001],aib[100001],m;
void update(int poz,int val){
    for(int i = poz;i<=n; i+=(i&-i))
        aib[i]+=val;
}
ifstream fin("aib.in");
ofstream fout("aib.out");
int query(int poz){
    int suma  = 0;
    for(int i = poz;i>=1;i-=(i&-i))
        suma+=aib[i];
    return suma;
}
int cb(int val){
    int st=1,dr=n;
    int pozmax=0;
    while(st<=dr){
        int mid=(st+dr)/2;
        int x=query(mid);
        if(x==val){
            pozmax=mid,dr=mid-1;
        }
        else if(x<val)
            st=mid+1;
        else
            dr=mid-1;
    }
    if(pozmax==0)
        return -1;
    return pozmax;
}
int32_t main(){
    fin>>n>>m;
    for(int i=1;i<=n;i++){
        fin>>v[i];
        update(i,v[i]);
    }
    while(m--){
        int t; fin>>t;
        if(t+1==1){
            int poz,val;
            fin>>poz>>val;
            update(poz,val);
           // v[poz]=val;
        }
        else if(t+1==2){
            int st,dr; fin>>st>>dr;
            fout<<query(dr)-query(st-1)<<'\n';
        }
        else{
            int val;
            fin>>val;
            fout<<cb(val)<<'\n';
        }
    }
    return 0;
}