#include <fstream>

const int MAX_N(100001);
const int LOG2(16);

int v [MAX_N];
int Bit [MAX_N];
int n;

inline int Lsb (int x)
{
	return x & -x;
}

inline void Update (int index, int val)
{
	while (index <= n)
	{
		Bit[index] += val;
		index += Lsb(index);
	}
}

inline int Query (int index)
{
	int result(0);
	while (index)
	{

		result += Bit[index];
		index -= Lsb(index);

	}
	return result;
}

int main (void)
{
	std::ifstream input("aib.in");
	int m, code, x, y;
	input >> n >> m;
	for (int i(1) ; i <= n ; ++i)
	{
		input >> v[i];
		Update(i,v[i]);
	}
	std::ofstream output("aib.out");
	while (m)
	{
		input >> code;
		if (code == 0 || code == 1)
			input >> x >> y;
		else
			input >> x;
		if (code == 0)
		{
			Update(x,y);
			v[x] += y;
		}
		else if (code == 1)
			output << Query(y) - Query(x - 1) << '\n';
		else
		{
			int value(0), index(0);
			for (int i(LOG2) ; i >= 0 ; --i)
				if (index + (1 << i) <= n && value + Bit[index + (1 << i)] <= x)
				{
					if (value + Bit[index + (1 << i)] == x && v[index + (1 << i)] == 0)
						continue;
					index += (1 << i);
					value += Bit[index];
				}
			output << (value == x ? index : -1) << '\n';
		}
		--m;
	}
	return 0;
}