#include <fstream>
#define N_MAX 102400

using namespace std;


int arb[2*N_MAX];
int n, m, n2;

int interogare2(int val, int st, int dr, int poz)
{
	if (arb[poz] < val)
		return -1;
	if (st==dr)
	{
		if (arb[poz] == val)
			return st;
		else 
			return -1;
	}
	if (arb[poz*2] >= val)
		return interogare2(val, st, (st+dr)/2, poz*2);
	else
		return interogare2(val-arb[poz*2], (st+dr)/2 +1, dr, poz*2+1);
}

int interogare(int a, int b, int st, int dr, int poz)
{
	if ((a<= st) && (dr <= b))
		return arb[poz];
	if ((b < st) || (a > dr))
		return 0;
	return interogare(a, b, st, (st+dr)/2, poz*2) + interogare(a, b, (st+dr)/2+1, dr, poz*2+1);
}

void adauga(int unde, int val)
{
	arb[unde]+=val;
	if (unde > 1)
		adauga(unde/2, val);
}

inline int pozitie(int unde)
{
	return n2+unde-1;
}


int main()
{
	ifstream in( "aib.in" );
	ofstream out( "aib.out" );
	
	int i, a, b, tip;
	in>>n>>m;
	n2=1;
	while (n2 < n)
	{
		n2 = n2 << 1;
	}
	for (i=1; i<=n; i++)
	{
		in>>a;
		adauga(pozitie(i), a);
	}
	for (i=1; i<=m; i++)
	{
		in>>tip;
		switch (tip)
		{
			case 0:
				in>>a>>b;
				adauga(pozitie(a), b);
				break;
			case 1:
				in>>a>>b;
				out<<interogare(a, b, 1, n2, 1)<<endl;
				break;
			case 2:
				in>>a;
				out<<interogare2(a, 1, n2, 1)<<endl;
				break;
		}
	}
	
	return 0;	
}