#include <stdio.h>
#include <string.h>
long v[10002],n,m;
long p2[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8191,16384,32768,65536,131072};
FILE *fin=fopen("aib.in","r");
FILE *fout=fopen("aib.out","w");

void aduna()
{ int a,b,poz;
 fscanf(fin,"%d %d", &a,&b);
 poz=0;
 while (a<=n)
  {
   v[a]+=b;
   while (!(a&p2[poz])) poz++;
   a+=p2[poz];
   poz++;
  }
}

void suma_int()
{ int a,b,poz,j; long s1,s2;
 fscanf(fin,"%d %d", &a,&b);
 s1=0; j=b; poz=0;
 while (j)
  {
   s1+=v[j];
   while (!(j&p2[poz])) poz++;
   j-=p2[poz];
   poz++;
  }
 s2=0; j=a-1; poz=0;
 while (j)
  {
   s2+=v[j];
   while (!(j&p2[poz])) poz++;
   j-=p2[poz];
   poz++;
  }
 fprintf(fout,"%ld\n",s1-s2);
}

void min_k()
{ int a,gasit,j,st,dr,poz,x; long s1;
 fscanf(fin,"%d", &a);
 st=1;dr=n; gasit=0; x=0;
 do
  {
   x=st+(dr-st)/2;
   s1=0; j=x; poz=0;
   while (j)
    {
     s1+=v[j];
     while (!(j&p2[poz])) poz++;
     j-=p2[poz];
     poz++;
    }
   if (s1==a) {gasit=x;}
      else
       if (s1>a) {dr=x-1;}
	  else {st=x+1;}
  }
 while (!gasit && dr>=st);
 if (!gasit) gasit=-1;
 fprintf(fout,"%ld\n",gasit);
}

int main()
{
 memset(v,0,sizeof(v));
 fscanf(fin,"%d %d",&n,&m);
 int i,j,x,poz;
 for (i=1;i<=n;i++)
  {
   fscanf(fin,"%d",&x);
   j=i; poz=0;
   while (j<=n)
    {
     v[j]+=x;
     while (!(j&p2[poz])) poz++;
     j+=p2[poz];
     poz++;
    }
  }

 int operatie,op;
 for (operatie=0;operatie<m;operatie++)
  {
   fscanf(fin,"%d",&op);
   switch (op)
    {
     case 0:{ aduna(); break;}
     case 1:{ suma_int(); break;}
     default: { min_k();}
    }
  }
 fclose(fin);
 fclose(fout);
 return 0;
}