#include<stdio.h>
int n,m;
unsigned int arb[100005];
unsigned int val;
const int p=1<<20;
int nrb(int x)
{
	return (x&(x-1))^x;
}
void adauga(int poz)
{
	arb[poz]+=val;
	while((poz+=nrb(poz))<=n)
		arb[poz]+=val;
}
unsigned int suma(int k)
{
	unsigned int s=0;
	while(k)
	{
		s+=arb[k];
		k-=nrb(k);
	}
	return s;
}
int spune()
{
	int i,j=0;
	unsigned int s;
	for(i=p; i; i>>=1)
	{
		if(i+j>n)
			continue;
		j+=i;
		s=suma(j);
		if(s==val)
			return j;
		if(s<val)
			continue;
		j-=i;
	}
	return -1;
}
int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%d%d",&n,&m);
	int in;
	int poz,a,b;
	for(int i=1; i<=n; i++)
	{
		scanf("%u",&val);
		adauga(i);
	}
	for(; m; m--)
	{
		scanf("%d",&in);
		if(!in)
		{
			scanf("%d%u",&poz,&val);
			adauga(poz);
		}
		else
		if(in==1)
		{
			scanf("%d%d",&a,&b);
			printf("%u\n",(unsigned int)suma(b)-suma(a-1));
		}
		else
		{
			scanf("%u",&val);
			printf("%d\n",spune());
		}
	}
	return 0;
}