#include <cstdio>

const unsigned int MAX_SIZE(100001);

unsigned int bit [MAX_SIZE];

inline void update (unsigned int index, unsigned int value, unsigned int n)
{
	unsigned int power(1);
	do
	{
		bit[index] += value;
		while (!(index & power))
			power <<= 1;
		index += power;
		power <<= 1;
	}
	while (index <= n);
}

inline unsigned int sum (signed int index, unsigned int n)
{
	unsigned int power(1);
	unsigned int sum(0);
	do
	{
		sum += bit[index];
		while (!(index & power))
			power <<= 1;
		index -= power;
		power <<= 1;
	}
	while (index > 0);
	return sum;
}

inline signed int check_sum (unsigned int value, unsigned int n)
{
	unsigned int index(1);
	while (index < n)
		index <<= 1;
	signed int start_index(0);
	do
	{
		if (start_index + index <= n && value >= bit[start_index + index])
		{
			start_index += index;
			value -= bit[start_index];
		}
		index >>= 1;
	}
	while (index && value);
	if (value)
		return -1;
	return start_index;
}

int main (void)
{
	std::freopen("aib.in","r",stdin);
	std::freopen("aib.out","w",stdout);
	unsigned int n, m;
	std::scanf("%u%u",&n,&m);
	unsigned int a, *a_ptr(&a);
	{
		unsigned int counter(1);
		do
		{
			std::scanf("%u",a_ptr);
			update(counter,a,n);
			++counter;
		}
		while (counter <= n);
	}
	char operation, *operation_ptr(&operation);
	unsigned int b, *b_ptr(&b);
	do
	{
		std::scanf("\n%c%u",operation_ptr,a_ptr);
		if (operation < '2')
		{
			std::scanf("%u",b_ptr);
			if (operation == '0')
				update(a,b,n);
			else
				std::printf("%d\n",sum(b,n) - sum(a - 1,n));
		}
		else
			std::printf("%d\n",check_sum(a,n));
		--m;
	}
	while (m);
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}