#include<fstream.h>


  ifstream f("aib.in");
  ofstream g("aib.out");
   long a[100001],n,m,i,suma,j,x,y,z;


void ph(int x,int poz)
{
 int p,c=0;
 while(poz<=n)
 {
  a[poz]+=x;
  p=poz;
  while((p/2)*2==p) p=p/2,c++;
  poz+=(1<<c);
  c=0;
 }
}


int func(int poz)
{
 int c=0,p,s=0;
 while(poz>=1)
 {
  s+=a[poz];
  p=poz;
  while((p/2)*2==p) p=p/2,c++;
  poz-=(1<<c);
  c=0;
 }
 return s;
}

int min(int st,int dr)
{
 int x,y;
 if(st>dr) return -1;
 else
 {
  x=(st+dr)/2;
  y=func(x);
  if(y>suma) return min(st,x-1);
  else if(y<suma) return min(x+1,dr);
  else return x;
 }

}

int main()
{
 f>>n>>m;
 for(i=1;i<=n;i++)
 {
  f>>x;
  ph(x,i);
 }
 for(i=1;i<=m;i++)
 {
  f>>x;
  if(x==0)
  {
   f>>y>>z;
   ph(z,y);
  }
  if(x==1)
  {
   f>>y>>z;
   g<<(func(z)-func(y-1))<<"\n";
  }
  if(x==2)
  {
   f>>suma;
   g<<min(1,n)<<"\n";
  }
 }
 return 0;
}