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