#include <cstdio>
#define DIM 100005

using namespace std;

int aib[DIM], N, M;
inline int thing (int bit) // you call this lsb, i call this thing :)
{
	return ( bit & (bit-1) ^ bit );
}
inline void update (int k, int val)
{
	while (k <= N)
	{
		aib [k] += val;
		k += thing (k);
	}
}
inline int query (int k)
{   
	int sum = 0;
	while (k > 0)
	{
		sum += aib [k];
		k -= thing (k);
	}
	return sum;
}
inline int bin_search (int val)
{
	int left = 0, right = N, find = -1, ans, mid;
	while (left <= right)
	{
		mid = (left+ ( (right - left) >> 1) );
		ans = query (mid);
		if (ans < val) left = mid + 1;
		else if (ans == val) find = mid, right = mid - 1;
		else if (ans > val) right = mid - 1;
	}
	return find;
}
void read ()
{   
	int a, b, type, x, i;
	scanf ("%d%d\n", &N, &M);
	for (i = 1; i <= N; i++)
	{
		scanf ("%d", &x);
		update (i, x);
	}
	for ( ; M--; )
	{
		scanf ("%d", &type);
		if (type == 0)
		{
			scanf ("%d%d\n", &a, &b);
			update (a, b);
		}
		else if (type == 1)
		{
			scanf ("%d%d\n", &a, &b);
			printf ("%d\n", query (b) - query (a-1));
		}
		else if (type == 2)
		{
			scanf ("%d\n", &a);
			printf ("%d\n", bin_search (a) );
		}
	}
}

int main ()
{
	freopen ("aib.in", "r", stdin);
	freopen ("aib.out", "w", stdout);
	read ();
	return 0;
}