#include <stdio.h>

#define Nmax 100100

int n,m,a[Nmax],op,x,y;

void up(int i,int nr)
{
	for(;i<=n;i+=i^(i-1)&i)
		a[i]+=nr;
}

int q(int i)
{
	int ret=0;
	for(;i>0;i-=i^(i-1)&i)
		ret+=a[i];
	return ret;
}

int cauta(int st,int dr)
{
	int tmp=q((st+dr)/2);
	if(st==dr)
		if(tmp==x)
			return st;
		else
			return -1;
	else
		if(x<=tmp)
			return cauta(st,(st+dr)/2);
		else
			return cauta((st+dr)/2+1,dr);
}

int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	int i,tmp1,tmp;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		{
			scanf("%d",&x);
			up(i,x);
		}
	for(i=1;i<=m;++i)
		{
			scanf("%d",&op);
			if(op==0)
				{
					scanf("%d%d",&x,&y);
					up(x,y);
				}
			else
				if(op==1)
				{
					scanf("%d%d",&x,&y);
					tmp=q(x-1);
					tmp1=q(y);
					printf("%d\n",tmp1-tmp);
				}
			else
				{
					scanf("%d",&x);
					printf("%d\n",cauta(1,n));
				}
		}

	return 0;
}