#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

const int N = 100010;
int n,m,a,b,c,aib[N],suma(int);
void aduna(int,int);
int main()
{
  f>>n>>m;
  for(a=1;a<=n;a++)
    {
      f>>b;
      aduna(a,b);
    }
  for(;m;m--)
    {
      f>>c>>a;
      if(c==0)
	{
	  f>>b;
	  aduna(a,b);
	}
      else if (c==1)
	{
	  f>>b;
	  g<<suma(b)-suma(a-1)<<'\n';
	}
      else
	{
	  int lo,hi,mi;
	  lo=0;hi=n;
	  while(hi-lo>1)
	    {
	      mi=(lo+hi)/2;
	      if(suma(mi)<a)
		lo=mi;
	      else
		hi=mi;
	    }
	  if(suma(hi)!=a)
	    hi=-1;
	  g<<hi<<'\n';
	}
    }
  return 0;
}

void aduna(int poz,int val)
{
  for(;poz<=n;poz+=(poz&(-poz)))aib[poz]+=val;
}
 int suma(int poz)
 {
   int val=0;
   for(;poz;poz-=(poz&(-poz)))val+=aib[poz];
   return val;
 }