#include <fstream>
#include <vector>
using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");
#define MAXN 100000

int AIB[MAXN + 1];
int n;
int smask;
void Update(int x, int val)
{
	for (; x <= n; x += x & (-x))
	{
		AIB[x] += val;
	}
}
int Query(int x)
{
	int sum = 0;
	for (; x; x -= x & (-x))
	{
		sum += AIB[x];
	}
	return sum;
}
int SearchSum(int sum)
{
	int poz = 0;
	int mask = smask;
	while (mask && poz <= n)
	{
		int tpoz = poz | mask;
		if (tpoz <= n)
		{
			if (AIB[tpoz] == sum)
			{
				return tpoz;
			}
			else if (AIB[tpoz] < sum)
			{
				sum -= AIB[tpoz];
				poz = tpoz;
			}
		}
		mask >>= 1;
	}
	return -1;
}
int main()
{
	int M;
	in >> n >> M;
	smask = 1;
	while ((smask << 1) <= n) smask <<= 1;
	for (int i = 0; i < n; i++)
	{
		int x;
		in >> x;
		Update(i + 1, x);
	}
	while (M--)
	{
		int opt, a, b;
		in >> opt;
		switch (opt)
		{
		case 0: 
			in >> a >> b;
			Update(a, b);
			break;
		case 1:
			in >> a >> b;
			out << Query(b) - Query(a - 1) << '\n';
			break;
		case 2:
			in >> a;
			out << SearchSum(a) << '\n';
			break;
		}
	}
}