#include <stdio.h>
#define nMax 100001
int n,m,i,x,y,mij,st,dr,d;
int a[nMax];
void add(int ind,int val)
{ int r;
r=0;
while(ind<=n)
    {
    a[ind]+=val;
    while(!(ind & (1<<r)))r++;
    ind+=(1<<r);
    r++;
    }
}
int sum(int ind)
{ int r,s;
r=0;
s=0;
while(ind>0)
    {
    s+=a[ind];
    while(!(ind & (1<<r)))r++;
    ind-=(1<<r);
    r++;
    }
return s;
}
int bs(int s)
{ int poz,d;
st=1; dr=n;
poz=-1;
while(st<=dr)
    {
    mij=(st+dr)/2;
    d=sum(mij);
    if(d<s)st=mij+1;
    else if(sum(mij)>s)dr=mij-1;
    else {
         poz=mij;
         dr=mij-1;
         }
    }
return poz;
}
int main()
{ int op;
freopen("aib.out","w",stdout);
freopen("aib.in","r",stdin);
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++)
    {
    scanf("%d ",&x);
    add(i,x);
    }
for(i=1;i<=m;i++)
    {
    scanf("%d ",&op);
    if(op==0){
             scanf("%d %d",&x,&y);
             add(x,y);
             }
    else if (op==1)
            {
            scanf("%d %d\n",&x,&y);
            printf("%d\n",sum(y)-sum(x-1));
            }
    else {
          scanf("%d\n",&x);
          printf("%d\n",bs(x));
         }
    }
fclose(stdout);
fclose(stdin);
return 0;
}