using namespace std;
#include<fstream>
#include<vector>
#include<algorithm>
#define nmax 100001
#define mic unsigned short int
vector<unsigned int> aib(nmax);
vector<mic>v(nmax);
unsigned int n;
ofstream g("aib.out");
inline int zeros(mic x)
{
	mic nr=0;
	x=x&(-x);
	while(x>1)
		++nr,x>>=1;
	return nr;
}
void update(mic poz,mic x)
{
	while(poz<=n)
	{
		aib[poz]+=x;
		poz+=(1<<zeros(poz));
	}
}
int query(mic a)
{
	unsigned int s=0;
	while(a>0)
	{
		s+=aib[a];
		a-=(1<<zeros(a));
	}
	return s;
}
int search(unsigned int k)
{
   unsigned int li=1,ls=n,mij,s;
   while(li<ls)
   {
	   mij=(li+ls)>>1;
	   s=query(mij);
	   s>k ? ls=mij :li=mij+1;
   }
   return (query(li)==k ?li :-1);
}
int main()
{
	
	mic i,m,op,a,b;
	unsigned int  k;
	ifstream f("aib.in");
	f>>n>>m;
	
	for(i=1;i<=n;i++)
	{	
		f>>v[i];
		update(i,v[i]);
	}

	for(i=1;i<=m;i++)
	{
		f>>op;
		if(op&1)
		{
			f>>a>>b;
			g<<query(b)-query(a-1)<<"\n";
		}
		else
			if(op)
			{
				f>>k;
				g<<search(k)<<"\n";
			}
			else
			{	f>>a>>b;
				update(a,b);
			}
	}
	f.close();
	g.close();
	return 0;
}