#include <cstdio>
int n,m;
int arb[200001];
int nr;
void update(int s,int e,int pos,int nod)
{
     if(s==e) arb[nod]+=nr;
     else
     {
         int mij=(s+e)/2;
         if(pos<=mij) update(s,mij,pos,2*nod);
         else update(mij+1,e,pos,2*nod+1);
         arb[nod]=arb[2*nod]+arb[2*nod+1];
     }
}
int query(int s,int e,int p1,int p2,int nod)
{
    if(p1==s&&p2==e) return arb[nod];
    else
    {
        int mij=(s+e)/2;
        if(p2<=mij) return query(s,mij,p1,p2,2*nod);
        else if(p1>mij) return query(mij+1,e,p1,p2,2*nod+1);
        return query(s,mij,p1,mij,2*nod)+query(mij+1,e,mij+1,p2,2*nod+1);
    }
}
int main()
{
    freopen ("aib.in","r",stdin);
    freopen ("aib.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
            scanf("%d",&nr);
            update(1,n,i,1);
    }
    int tip,n1,n2;
    for(int i=1;i<=m;i++)
    {
            scanf("%d",&tip);
            if(tip==0)
            {
                      scanf("%d%d",&n1,&nr);
                      update(1,n,n1,1);
            }
            else if(tip==1)
            {
                 scanf("%d%d",&n1,&n2);
                 printf("%d\n",query(1,n,n1,n2,1));
            }
            else if(tip==2)
            {
                 scanf("%d",&n1);
                 int s=1,e=n,rasp=0;
                 while(s<=e)
                 {
                            int mij=(s+e)/2,val=query(1,n,1,mij,1);
                            if(val==n1)
                            {
                                       rasp=mij;
                                       e=mij-1;
                            }
                            else if(val<n1)
                            {
                                 s=mij+1;
                            }
                            else e=mij-1;
                 }
                 if(rasp==0) rasp--;
                 printf("%d\n",rasp);
            }
    }
}