#include<fstream>
#define NMAX 100010

using namespace std;

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

int n, m, a[NMAX];

int ult1(int x)
{
	return (x^(x-1))&x;
}

int suma(int poz, int lim)
{
	int s=0;
	for (; poz>lim; poz-=ult1(poz)) s+=a[poz];
	return s;
}

void Citeste()
{
	int i, x;
	f>>n>>m;
	for (i=1; i<=n; ++i)
	{
		f>>x;
		a[i]=x+suma(i-1, i-ult1(i));
	}
}

void Update(int poz, int y)
{
	for(; poz<=n; poz+=ult1(poz)) a[poz]+=y;
}

int cauta(int k)
{
	int st=1, dr=n, mij, ok=0, s;
	while (st<=dr)
	{
		mij=(st+dr)>>1;
		s=suma(mij, 0);
		if (s<k) st=mij+1;
		else dr=mij-1, ok=mij;
	}
	if (suma(ok, 0)==k) return ok;
	return -1;
}

void Solve()
{
	int x, y, op, k;
	
	while (m--)
	{
		f>>op;
		if (op==0)
		{
			f>>x>>y;
			Update(x, y);
		}
		else 
			if (op==1)
			{
				f>>x>>y;
				g<<suma(y, 0)-suma(x-1, 0)<<"\n";
			}
			else
			{
				f>>k;
				g<<cauta(k)<<"\n";
			}
	}
}

int main()
{
	Citeste();
	
	Solve();
	
	f.close();
	g.close();
	return 0;
}