#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, start;

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

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

int querry (int pos, int ratie, int val)
{
	if (aib[pos+ratie] == val)
		return pos + ratie;
	if (aib[pos+ratie] < val)
		return querry(pos + ratie, ratie/2, val - aib[pos+ratie]);
	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;
			start = bgn;
			while (aib[start] > a)
				start>>=1;
			fo << querry(0, start, a) << '\n';
		}
	}
	return 0;
}