#include<fstream.h>
int aib[100100],n,u=1;
void update(int i, int add)
{
	while(i<=n)
	{
		aib[i]+=add;
		i=(i|(i-1))+1;
	}
}
int suma(int i)
{
	int s=0;
	while(i)
	{
		s+=aib[i];
		i&=(i-1);
	}
	return s;
}
int query(int x)
{
	int i=0,p=u;
	while(p)
	{
		if(i+p<=n)
			if(x>=aib[i+p])
			{
				x-=aib[i+p];
				i+=p;
				if(!x)
					return i;
			}
		p>>=1;
	}
	return -1;
}
int main()
{
	int m,op,i;
	ifstream f("aib.in");
	ofstream g("aib.out");
	f>>n>>m;
	while(u<n)
		u<<=1;
	for(i=1;i<=n;i++)
	{
		f>>op;
		update(i,op);
	}
	while(m--)
	{
		f>>op;
		if(!op)
		{
			f>>i>>op;
			update(i,op);
		}
		else
			if(op==1)
			{
				f>>i>>op;
				g<<suma(op)-suma(i-1)<<'\n';
			}
			else
			{
				f>>i;
				g<<query(i)<<'\n';
			}
	}
	return 0;
}