#include<stdio.h>
#include<math.h>
FILE *f,*g;
long mij,smij,p,s,j,op,n,c[100005],aux,suma1,suma2,x,y,okk,m,i,bz[100005];
long baza(long x)
{ int ok=1; long nr=0;
  while(x>0&&ok)
   { if(x%2==0) nr++; else ok=0;
     x/=2;
   }
  return nr;
}
void modificare(long x,long y)
{ p=x;
  while(p<=n)
   { if(p<=n) c[p]=c[p]+y;
     p=p+bz[p];
   }
}
long suma(long x,long y)
{ suma1=0; suma2=0; x--;
  p=x; while(p) { suma1+=c[p]; p-=bz[p]; }
  p=y; while(p) { suma2+=c[p]; p-=bz[p]; }
  return suma2-suma1;
}
long ctbinara(long x,long l1, long l2)
{smij=suma(1,(l1+l2)/2); if(l1>l2) return -1;
  if(smij==x) return (l1+l2)/2;
  else if(smij>x) return ctbinara(x,l1,(l1+l2)/2-1);
   else return ctbinara(x,(l1+l2)/2+1,l2);
}
int main()
{ f=fopen("aib.in","r"); g=fopen("aib.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  for(i=1;i<=n;i++) bz[i]=pow(2,baza(i));
  for(i=1;i<=n;i++) { fscanf(f,"%ld",&aux); modificare(i,aux); }
  for(i=1;i<=m;i++)
   { fscanf(f,"%ld",&op);
     if(op==0) { fscanf(f,"%ld%ld",&x,&y); modificare(x,y); }
     else if(op==1) { fscanf(f,"%ld%ld",&x,&y); fprintf(g,"%ld\n",suma(x,y)); }
     else
      { fscanf(f,"%ld",&x); okk=1;
	 fprintf(g,"%ld\n",ctbinara(x,1,n));
      }
   }
  fclose(g);
  return 0;
}