#include <stdio.h>

#define nmax 100005

int n, s, aib [nmax];


inline int nr0 (int x)
{
	return x & ((x-1) ^ x);
}

void update (int p, int v)
{
	while (p <= n) 
	{
		aib [p] += v;
		p += nr0 (p);
		//fprintf(stderr, "%d %d\n", p, nr0(p)); 
	}
}

int query (int p)
{
	int S=0;
	while (p)
	{
		S += aib [p];
		p -= nr0 (p);
	}	
	return S;
}

int cautare (int v)
{
	int i, step=s;
	--v;
	for (i=0; step; step >>= 1) 
		if (i+step <= n && query (i+step) <= v) 
			i += step;
	++v;
	++i;
	//fprintf(stderr, "v=%d i=%d quey=%d\n", v, i, query(i)); 
	if (query (i) != v)
	       return -1;
	return i;	
}


void rez ()
{
	int i, m, v, cod, x, y;
	scanf ("%d%d", &n, &m);
	for (s=1; s <= n; s <<= 1); 
	for (i=1; i <= n; ++i) 
	{
		scanf ("%d", &v);
		update (i, v);
	}

//for (i=1; i <= n; ++i) 
//	fprintf(stderr, "%d ", aib [i]); 

	for (i=1; i <= m; ++i) 
	{
		scanf ("%d", &cod);
		//fprintf(stderr, "%d\n", cod); 
		if (!cod)
		{
			scanf ("%d%d", &x, &y);
			update (x, y);
		}
		else
		{
			if (cod == 1)
			{
				scanf ("%d%d", &x, &y);
				printf ("%d\n", query (y)-query (x-1));
			}
			else
			{
				scanf ("%d", &x);
				printf ("%d\n", cautare (x));
			}	
		}
	}
}

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