#include <fstream>
#define NMAX 100000
using namespace std;

int v[NMAX+1], n, m, op, a, b;

ifstream f("aib.in");
ofstream g("aib.out");

void Update(int i, int x)
{	while (i<=n)
	{	v[i]+=x;
		i+=(i&-i);
	}
}

int Sum(int x)
{	if (x)
		return v[x]+Sum(x&(x-1));
	else
		return 0;
}

int BinSearch(int x)
{	int incr=1;
	while (incr*2<=n)
		incr<<=1;
	int poz=0;
	while (incr)
	{	if (v[incr]<=x)
		{	x-=v[incr];
			poz+=incr;
		}
		incr>>=1;
	}
	if (poz)
		return poz;
	else
		return -1;
}

int main()
{	f>>n>>m;
	int i;
	for (i=1; i<=n; ++i)
	{	int x;
		f>>x;
		Update(i, x);
	}
	for (; m; --m)
	{	f>>op;
		if (op==0)
		{	f>>a>>b;
			Update(a, b);
		}
		else
		{	if (op==1)
			{	f>>a>>b;
				g<<Sum(b)-Sum(a-1)<<'\n';
			}
			else
			{	f>>a;
				g<<BinSearch(a)<<'\n';
			}
		}
	}
    return 0;
}