#include <fstream>
#define NM 100100
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
int n,m,p,sp[NM],v[NM],C[NM],q,a,b,x,k,S,st,dr,mij;
int sum(int x);
int main()///aib actually
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        sp[i]=sp[i-1]+v[i];
        p=(i^(i-1))&i;
        C[i]=sp[i]-sp[i-p];
    }/*
    for(int i=1;i<=n;i++)
        cout<<C[i]<<' ';
    cout<<'\n'<<'\n';*/
    for(int i=1;i<=m;i++)
    {
        cin>>q>>a;
        if(q<2)
            cin>>b;
        if(q==0)
        {
            x=a;
            do{
                C[x]=C[x]+b;
                p=(x^(x-1))&x;
                x=x+p;
            }while(x<=n);
        }
        else if(q==1)
        {
            S=sum(b)-sum(a-1);
            cout<<S<<'\n';
        }
        else{
            st=1;dr=n;
            k=-1;mij=0;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                S=sum(mij);
                if(S<a)
                    st=mij+1;
                else if(S>a)
                    dr=mij-1;
                else k=mij,dr=mij-1;
            }
            cout<<k<<'\n';
        }
    }
    return 0;
}
int sum(int x)
{
    int s=0;
    do{
        s=s+C[x];
        p=(x^(x-1))&x;
        x=x-p;
    }while(x>0);
    return s;
}