#include<fstream.h>
#define nx 100005
#define zeros(x) ((x^(x-1))&x)
int a[nx],n;
void add(int x,int what)
 {
  for (int i=x;i<=n;i+=zeros(i))
     a[i]+=what;
 }
int doit (int x)
 {
  int i,r=0;
  for (i=x;i>0;i-=zeros(i))
     r+=a[i];
  return r;
 }
int main()
 {
  ifstream be ("aib.in");
  ofstream ki ("aib.out");
  int m;
  be>>n>>m;
  int i,r,x,y,st,dr,o,ok,mij;
  for (i=1;i<=n;++i)
   {
    be>>x;
    add(i,x);
   }
  for (i=1;i<=m;++i)
   {
    be>>o;
    if (!o)
     {
      be>>x>>y;
      add(x,y);
     }
    if (o==1)
     {
      be>>x>>y;
      ki<<doit(y)-doit(x-1)<<'\n';
     }
    if (o==2)
     {
      be>>x;
      int st=1,dr=n;
      ok=0;
      while (st<=dr)
       {
	mij=st+(dr-st)/2;
	int r=doit(mij);
	if (r>x)
	  dr=mij-1;
	else
	 if (r<x)
	   st=mij+1;
	 else
	   ok=1,st=dr+1;
       }
      if (!ok)
	ki<<-1<<'\n';
      else
	{
	 while (doit(mij)==x) mij--;
	 ki<<mij+1<<'\n';
	}
     }
   }
  be.close();
  ki.close();
  return 0;
 }