#include <iostream>
#include <fstream>
using namespace std;

int n,nq,q,a,b,pos,val,nr,i,mid,ans,l,r;
int aib[100005];

int lsb(int nr)
{
	int ax=-nr;
	return (ax&nr);
}


void add(int pos,int nr)
{
	int i;
	for (i=pos;i<=n;i+=lsb(i))
		aib[i]+=nr;
}

int query(int pos)
{
	int i;
	int val=0;
	for (i=pos;i>0;i-=lsb(i))
		val+=aib[i];
	return val;
}

int sum(int k,int val)
{
	int s=query(k);
	if (s<val)
		return -1;
	if (s>val)
		return 1;
	if (s==val)
		return 0;
	
}

int main(void)
{
	FILE * f;
	f=fopen("aib.in","r");
	ofstream g("aib.out");
	
	fscanf(f,"%d%d",&n,&nq);
	for (i=1;i<=n;i++)
	{
		fscanf(f,"%d",&nr);
		add(i,nr);
	}
	
	for (i=1;i<=nq;i++)
	{
		fscanf(f,"%d",&q);
		if (q==0)
		{
			fscanf(f,"%d%d",&pos,&val);
			add(pos,val);
		}
		if (q==1)
		{
			fscanf(f,"%d%d",&a,&b);
			val=0;
			val=val+query(b);
			val=val-query(a-1);
			g<<val<<'\n';
		}
		if (q==2)
		{
			fscanf(f,"%d",&val);
			l=1;
			r=n;
			ans=0;
			while (l<=r)
			{
				mid=(l+r)/2;
				if (sum(mid,val)==0)
				{
					ans=mid;
					r=mid-1;
				}
				if (sum(mid,val)==-1)
					l=mid+1;
				if (sum(mid,val)==1)
					r=mid-1;
			}
			if (ans==0)
				g<<"-1\n";
			else
				g<<ans<<'\n';
		}
	}
	
	return 0;
}