#define DM 100001
#include <fstream>
using namespace std;

ifstream fi ("aib.in");
ofstream fo ("aib.out");
int n, m, c, a, b, aib[DM], v[DM], bgn = (1<<30);

void update (int pos, int val)
{
	int cpos;
	while (pos <= n)
	{
		cpos = pos - 1;
		cpos = cpos^pos;
		cpos = cpos&pos;
		aib[pos]+=val;
		pos+=cpos;
	}
}

int suma (int pos)
{
	int cpos, sma = 0;
	while (pos)
	{
		cpos = pos - 1;
		cpos = cpos^pos;
		cpos = pos&cpos;
		sma+=aib[pos];
		pos-=cpos;
	}
	return sma;
}

int query (int pos, int ratie, int val)
{
	while (val && ratie)
	{
		if (aib[pos+ratie] <= val)
		{
			val-=aib[pos+ratie];
			pos+=ratie;
			ratie>>=1;
		}
		else
			ratie>>=1;
	}
	if (!val)
		return pos;
	return -1;
}

int main()
{
	fi >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		fi >> v[i];
		update(i, v[i]);
	}
	while (bgn > n)
		bgn>>=1;
	for (int i = 1; i <= m; ++i)
	{
		fi >> c;
		if (c == 0)
		{
			fi >> a >> b;
			update(a, b);
		}
		else if (c == 1)
		{
			fi >> a >> b;
			fo << suma(b) - suma(a - 1) << '\n';
		}
		else 
		{
			fi >> a;
			fo << query(0, bgn, a) << '\n';
		}
	}
	return 0;
}