#include <iostream>
#include <fstream>

using namespace std;

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

#define zeros(pos) ( (pos ^ (pos - 1)) & pos )

int n, q;
int aib[(1 << 18) + 1];

void add(int pos, int val)
{
	for (int i = pos; i <= n; i += zeros(i))
		aib[i] += val;
}

int calc(int pos)
{
	int ret = 0;
	for (int i = pos; i > 0; i -= zeros(i))
		ret += aib[i];
	return ret;
}

int main()
{
	in >> n >> q;
	for (int i = 1; i <= n; i++)
	{
		int x;
		in >> x;
		add(i, x);
	}
	while (q--)
	{
		int t, a, b;
		in >> t;
		if (t == 0)
		{
			in >> a >> b;
			add(a, b);
		}
		else if (t == 1)
		{
			in >> a >> b;
			out << calc(b) - calc(a - 1) << '\n';
		}
		else
		{
			in >> a;
			b = 0;
			for (int step = (1 << 20); step; step >>= 1)
				if (b + step <= n && calc(b + step) <= a)
					b += step;
			if (calc(b) == a)
				out << b << '\n';
			else
				out << -1 << '\n';
		}
	}
}