#include<stdio.h>

long n,m,v[1<<17];

inline long cautb(long temp){return ((temp^(temp-1))&temp);}

void update(long poz,long val)
{
	while(poz<=n)
	{
		v[poz]+=val;
		poz+=cautb(poz);
	}
}
long add(long poz)
{
long sum=0;
	while(poz)
	{
		sum+=v[poz];
		poz-=cautb(poz);
	}
return sum;
}
long search(long temp)
{     
long poz=0,pow=1;
	while(pow<=n){ pow<<=1;}
	while(pow)
	{
		if( poz+pow<=n)
         {
            if(temp>=v[pow+poz])
            {
                poz+=pow;
				temp-=v[poz];
                if (!temp) return poz;
            }
         }
		pow>>=1;
    }
     
return -1;
}

int main()
{
long stare,x,y,temp,i;
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
	
scanf("%ld%ld",&n,&m);
for (i=1;i<=n;++i)
	{
		scanf("%ld",&temp);
		update(i,temp);
	}
for (i=1;i<=m;++i)
	{
		scanf("%ld",&stare);
		if (stare==0)
			{
			scanf("%ld%ld",&x,&y);	
			update(x,y);
			}
		else if (stare==1)
			{
			scanf("%ld%ld",&x,&y);	
			printf("%ld\n",add(y)-add(x-1));
			}
		else
			{
			scanf("%ld",&temp);
			printf("%ld\n",search(temp));
			}
	}

return 0;
}