#include<stdio.h>

long n,m,v[1<<17];

inline long cautb(long temp){return (temp^(temp-1))&temp;}

void update(long poz,long val)
{
	while(poz<=n)
	{
		v[poz]+=val;
		poz+=cautb(poz);
	}
}
long add(long poz)
{
long sum=0;
	while(poz>=1)
	{
		sum+=v[poz];
		poz-=cautb(poz);
	}
return sum;
}
long search(long temp)
{
long poz=1,sum=0,k=0;
	while(sum<temp)
	{
		sum+=v[poz];
		++k;
		poz+=cautb(poz);
	}
if (sum==temp)
	return k;
return -1;
}

int main()
{
long stare,x,y,temp,i;
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
	
scanf("%ld%ld",&n,&m);
for (i=1;i<=n;++i)
	{
		scanf("%ld",&temp);
		update(i,temp);
	}
for (i=1;i<=m;++i)
	{
		scanf("%ld",&stare);
		if (stare==0)
			{
			scanf("%ld%ld",&x,&y);	
			update(x,y);
			}
		else if (stare==1)
			{
			scanf("%ld%ld",&x,&y);	
			printf("%ld\n",add(y)-add(x-1));
			}
		else
			{
			scanf("%ld",&temp);
			printf("%ld\n",search(temp));
			}
	}

return 0;
}