#include<stdio.h>
#define z(x) x^(x-1)&x
int h[100001],m,n,i,j,c,a,b;
inline void add(int poz, int nr)
{
	while(poz<=n)
	{
		h[poz]+=nr;
		poz+=z(poz);
	}
}
inline int suma(int a, int b)
{
	int s=0;
	while(b>0)
	{
		s+=h[b];
		b-=z(b);
	}
	while(a>0)
	{
		s-=h[a];
		a-=z(a);
	}
	return s;
}
inline int gas(int s)
{
	if(s<h[1])return -1;
	int i=0,x;
	while(1<<i<=n)
		if(h[1<<i]>s)break;
			else ++i;
	--i;
	x=1<<i;
	s-=h[x];
	for(i=i-1;i>=0 && s!=0;--i)
	{
		if(x+1<<i<=n)
		if(h[x+1<<i]<=s)
		{
			x+=1<<i;
			s-=h[x];
		}
	}
	if(s==0)return x;
	return -1;
}
int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&a);
		add(i,a);
	}
	for(i=0;i<m;++i)
	{
		scanf("%d",&c);
		switch(c)
		{
		case 0:
			{
				scanf("%d%d",&a,&b);
				add(a,b);
				break;
			}
		case 1:
			{
				scanf("%d%d",&a,&b);
				printf("%d\n",suma(a-1,b));
				break;
			}
		case 2:
			{
				scanf("%d",&a);
				printf("%d\n",gas(a));
				break;
			}
		}
	}
	return 0;
}