#include<stdio.h>
#include<math.h>
FILE *f,*g;
long mij,smij,l1,l2,p,s,j,op,n,c[100005],aux,suma1,suma2,x,y,okk,m,i; int 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;
}
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;
	l1=1; l2=n;
	while(l1<=l2&&okk)
	 { mij=(l1+l2)/2; smij=suma(1,mij);
	   if(smij==x) { fprintf(g,"%ld\n",mij); okk=0; }
	    else if(smij>x) l2=mij-1;
	     else l1=mij+1;
	 }
	if(okk) fprintf(g,"-1\n");
      }

   }
  fclose(g);
  return 0;
}