#include<cstdio>
int h[100013],m,n,i,j,c,a,b;
inline int z(int x)
{
	return (x^(x-1)&x);
}
inline void add(int poz, int nr)
{
	while(poz<=n)
	{
		h[poz]+=nr;
		poz+=z(poz);
	}
}
inline int sum(int a, int b)
{
	int s=0;
	while(b!=0)
	{
		s+=h[b];
		b-=z(b);
	}
	while(a!=0)
	{
		s-=h[a];
		a-=z(a);
	}
	return s;
}
inline int srch(int s)
{
	int i=0,x;
	while(h[1<<(i+1)]<=s && 1<<(i+1)<=n)++i;
	x=1<<i;--i;s-=h[x];
	while(i>=0 && s!=0)
	{
		if(h[x+1<<i]<=s) 
		{
			x+=1<<i;
			s-=h[x];
		}
		--i;
	}
	if(s==0)return x;
	return -1;
}
int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&a);
		add(i,a);
	}
	for(j=0;j<m;++j)
	{
		scanf("%d",&c);
		switch(c)
		{
		case 0:
			{
				scanf("%d%d",&a,&b);
				add(a,b);
				break;
			}
		case 1:
			{
				scanf("%d%d",&a,&b);
				printf("%d\n",sum(a-1,b));
				break;
			}
		case 2:
			{
				scanf("%d",&a);
				printf("%d\n",srch(a));
			}
		}
	}
	return 0;
}