#include <stdio.h>

unsigned n,m,v[100005],x[100005];



unsigned abi(int i,int j)
{
    int mij;
    if(i==j){
        x[i]=v[i];
        return v[i];
    }
    mij=(i+j)/2;
    x[mij]=abi(i,mij)+abi(mij+1,j);
    return x[mij];
}


unsigned query(int i,int j,int st,int dr)
{
    unsigned mij,sst,sdr;
    if(i>dr || j<st ||st>dr)
        return 0;
    mij=(st+dr)/2;
    if(st==dr)
        return v[st];
    if(i<=st && j>=dr)
        return x[mij];
    sst=query(i,j,st,mij);
    sdr=query(i,j,mij+1,dr);
    return sst+sdr;
}

int actualizare(int i,int j,int st, int dr,int k)
{
    int mij,nst,ndr,act;

    if(i>dr || j<st ||st>dr)
        return 0;
    if(dr==st)
    {
        v[st]+=k;
        return 1;
    }

    mij=(st+dr)/2;
    nst=actualizare(i,j,st,mij,k);
    ndr=actualizare(i,j,mij+1,dr,k);
    act=nst+ndr;
    x[mij]+=act*k;
    return act;
}

int cauta(int st,int dr,int a)
{
    unsigned mij=(st+dr)/2,sst;
    if(x[mij]<a || st>dr)
        return -1;
    if(st==dr && v[st]==a)
        return st;
    if(x[mij]==a)
        return dr;
    sst=query(1,mij,1,mij);
    if(sst>=a)
        cauta(1,mij,a);
    else
        cauta(mij+1,dr,a-sst);
}

int main()
{
    unsigned i,j,k,o,a,b,p1,p2;
    FILE *f,*g;

    f=fopen("aib.in","r");
    g=fopen("aib.out","w");

    fscanf(f,"%d%d",&n,&m);


    for (i=1;i<=n;i++)
        fscanf(f,"%d",&v[i]);

    abi(1,n);

    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&o,&a);
        if(o==0)
        {
            fscanf(f,"%d",&b);
            actualizare(a,a,1,n,b);
        }
        if(o==1)
        {
            fscanf(f,"%d",&b);
            fprintf(g,"%d\n",query(a,b,1,n));
        }
        if(o==2)
                fprintf(g,"%d\n",cauta(1,n,a));
    }

}