#include<cstdio>
using namespace std;
int aib[100005],p,n;
int lsb(int x)
{
	return ((x^(x-1))+1)>>1;
}

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

int query(int pos)
{
	int ans=0;
	while(pos)
	{
		ans+=aib[pos];
		pos-=lsb(pos);
	}
	return ans;
}
int bs(int k)
{
	int val=k,ans=0;
	for(int i=p-1;i>=0;i--)
	{
		if(ans+(1<<i)<=n)
			if(aib[ans+(1<<i)]<val)
			{
				ans+=(1<<i);
				val-=aib[ans];
			}
	}
	if(query(ans+1)==k)
		return ans +1;
	return -1;
}
int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	int m,val,semn,a,b,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		{
		scanf("%d",&val);
		update(i,val);
		}
	p=0;
	val=1;
	while(val*2<=n)
	{
		val*=2;
		p++;
	}
	p = 17;
	for(i=1;i<=m;i++)
		{
			scanf("%d",&semn);
			if(semn==0)
			{
				scanf("%d%d",&a,&b);
				update(a,b);
			}
			else
			if(semn==1)
			{
				scanf("%d%d",&a,&b);
				printf("%d\n",query(b)-query(a-1));
			}
			else
				{
					scanf("%d",&a);
					printf("%d\n",bs(a));
				}
		}
	return 0;
}