#include <fstream>
#include <vector>

inline void bit_update (std::vector<unsigned int> &bit, unsigned int index, unsigned int value, unsigned int size)
{
	unsigned int power(1);
	while (index <= size)
	{
		while (!(index & power))
			power <<= 1;
		bit[index] += value;
		index += power;
		power <<= 1;
	}
}

inline unsigned int bit_sum (std::vector<unsigned int> &bit, unsigned int index, unsigned int size)
{
	unsigned int sum(0), power(1);
	while (index)
	{
		while (!(index & power))
			power <<= 1;
		sum += bit[index];
		index -= power;
		power <<= 1;
	}
	return sum;
}

inline signed int bit_search_sum (std::vector<unsigned int> bit, unsigned int value, unsigned int size)
{
	signed int left(0), right(size + 1), middle(size), best(right);
	unsigned int sum;
	if (bit_sum(bit,middle,size) == value)
		best = middle;
	while (middle)
	{
		middle = (left + right) >> 1;
		sum = bit_sum(bit,middle,size);
		if (value < sum)
		{
			if (right > middle)
				right = middle;
			--middle;
		}
		else if (value > sum)
		{
			if (left < middle)
				left = middle;
			++middle;
		}
		else
		{
			if (best > middle)
				best = middle;
			right = middle;
			--middle;
		}
		if (middle <= left || middle >= right)
			break;
	}
	if (best > size)
		return -1;
	return best;
}

int main (void)
{
	unsigned int n, m;
	std::ifstream input("aib.in");
	input >> n >> m;
	std::vector<unsigned int> bit(n + 1,0); // b.i.t. - binary indexed tree
	unsigned int a;
	for (unsigned int counter(1) ; counter <= n ; ++counter)
	{
		input >> a;
		bit_update(bit,counter,a,n);
	}
	char option;
	unsigned int b;
	std::ofstream output("aib.out");
	do
	{
		input >> option >> a;
		if (option < '2')
		{
			input >> b;
			if (option == '0')
				bit_update(bit,a,b,n);
			else
				output << bit_sum(bit,b,n) - bit_sum(bit,a - 1,n) << '\n';
		}
		else
			output << bit_search_sum(bit,a,n) << '\n';
		--m;
	}
	while (m);
	input.close();
	output.close();
	return 0;
}