#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int p,cat,n,i,j,nr,sum[400000],l1,l2,a,b,x,m,k,o,s;

void update(int nr,int st,int dr)
{
	if(st==dr)
	{
		sum[nr]+=cat;
		return;
	}
	int md=(st+dr)/2;
	if(p<=md)   update(nr*2,st,md);
	else        update(nr*2+1,md+1,dr);
	sum[nr]=sum[nr*2]+sum[nr*2+1];
}

int queab(int nr,int st,int dr)
{
	if(st>=a&&dr<=b)    return sum[nr];
	int md=st+(dr-st)/2,r=0;
	if(max(st,a)<=min(md,b))    r+=queab(nr*2,st,md);
	if(max(md+1,a)<=min(dr,b))    r+=queab(nr*2+1,md+1,dr);
	return r;
}

int quek(int nr,int st,int dr)
{
	if(st==dr)  
	{	
		s+=sum[nr];
		return st;	
	}
	int md=st+(dr-st)/2,p=0;
	if(sum[nr*2]>=k)    p=quek(nr*2,st,md);
	else
	{
		k-=sum[nr*2];
		s+=sum[nr*2];
		p=quek(nr*2+1,md+1,dr);
	}
	return p;
}

int main()
{
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		p=i;
		fin>>cat;
		update(1,1,n);
	}
	for(i=1;i<=m;i++)
	{
		fin>>o;
		if(o==0)
		{
			fin>>p>>cat;
			update(1,1,n);
		}
		if(o==1)
		{
			fin>>a>>b;
			fout<<queab(1,1,n)<<"\n";
		}
		if(o==2)
		{
			fin>>k;
			s=0;	nr=k;
			o=quek(1,1,n);
			if(s==nr)	fout<<o<<"\n";
			else	fout<<"-1\n";
		}
	}
	return 0;
}