#include <cstdio>
using namespace std;
int S[150003],n;

void adauga(int poz, int x)
{
	do
	{
		S[poz]+=x;
		poz+=((poz^(poz-1))&poz);
	}
	while (poz<=n);
}

int suma(int x)
{  int sum=0;
   do
   {
	   sum+=S[x];
	   x-=((x^(x-1))&x);
   }
   while (x>0);
   return sum;
}

int min_k(int s)
{ int st=1,dr=n,poz=0;
  while (st<=dr)
  {
	int mij=(st+dr)/2;
	int smij=suma(mij);
	if (smij==s) {poz=mij; break;}
		else
		 if (smij<s) {st=mij+1;}
			 else dr=mij-1;
  }  
  if (!poz) return -1;  
  return poz;
}

int main()
{
	FILE *fin=fopen("aib.in","r");
	FILE *fout=fopen("aib.out","w");
	int T;
	fscanf(fin,"%d%d",&n,&T); S[0]=0;
	for (int i=1;i<=n;++i) 
	    { int x;
			fscanf(fin,"%d",&x);
			adauga(i,x);
		}
	while (T--)
	{   int op,a,b;
		fscanf(fin,"%d",&op);
		switch (op)
		{
			case 0: { fscanf(fin,"%d %d",&a,&b); adauga(a,b); break;}
			case 1: { fscanf(fin,"%d %d",&a,&b); fprintf(fout,"%d\n",suma(b)-suma(a-1)); break;}
			case 2:	{ fscanf(fin,"%d",&a); fprintf(fout,"%d\n",min_k(a));}
		}
	}	
	fclose(fin); fclose(fout);
	return 0;
}