#include<stdio.h>
#define N_MAX 131072

int arb[131072];

int adauga(int val, int unde, int poz, int st, int dr)
{
	if ((st<=unde) && (unde<=dr))
	{
		arb[poz]+=val;
		if (st==dr)
		{
			return 0;
		}
		adauga(val, unde, poz*2, st, (st+dr)/2);
		adauga(val, unde, poz*2+1, (st+dr)/2+1, dr);
	}
	return 0;
}

int cere(int L, int R, int poz, int st, int dr)
{
	if ((R<st) || (L>dr))
		return 0;
	if ((L<=st)&&(dr<=R))
		return arb[poz];
	return cere(L, R, poz*2, st, (st+dr)/2)+ cere(L, R, poz*2+1, (st+dr)/2+1, dr);
}

int main()
{
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);
	int n, m, i, a, b, c, st, dr, mij;
	scanf("%d %d", &n, &m);
	for (i=1; i<=n; i++)
	{
		scanf("%d", &a);
		adauga(a, i, 1, 1, n);
	} 
	for (i=1; i<=m; i++)
	{
		scanf("%d", &c);
		if (c==0)
		{
			scanf("%d %d", &a, &b);
			adauga(b, a, 1, 1, n);
			continue;
		}

		if (c==1)
		{
			scanf("%d %d", &a, &b);
			printf("%d\n", cere(a, b, 1, 1, n));
			continue;
		}
		
		if (c==2)
		{
			scanf("%d", &a);
			st=1;
			dr=n;
			while (st!=dr)
			{
				mij=(st+dr)/2;
				if (cere(1, mij, 1, 1, n)>=a)
					dr=mij;
				else
					st=mij+1;
			}
			if (arb[1]<a) st=-1;
			printf("%d\n", st);
			continue;
		}
	//*/	
	}
	//printf("%d", cere(1, 1, 1, 1, n));
	
	fclose(stdout);
	return 0;
}