#include <fstream>
using namespace std;

const int NMAX = 1<<17+8;
const char Input[]="aib.in";
const char Output[]="aib.out";

ifstream fin(Input);
ofstream fout(Output);

int arbSum[NMAX],pos,val,start,final,sum=0,k,n,m;

inline void update(int node,int left,int right)
{
	int center;
	if(left==right)
	{
		arbSum[node]+=val;
		return ;
	}
	center=(left+right)/2;
	if(pos<=center)
		update(2*node,left,center);
	else
		update(2*node+1,center+1,right);
	arbSum[node]=arbSum[2*node]+arbSum[2*node+1];
}

inline void query(int node,int left,int right)
{
	int center;
	if(start<=left &&  right<=final)
	{
		sum+=arbSum[node];
		return;
	}
	center=(left+right)/2;
	if(start<=center)
		query(2*node,left,center);
	if(center<final)
		query(2*node+1,center+1,right);
}

inline int cauta(int k)
{
	sum=0;
	start=1,final=n;
	int li=1,ls=n,center;
	while(li<=ls)
	{
		center=(li+ls)/2;
		sum=0;
		final=center;
		query(1,1,n);
		if(sum>k)
			ls=center-1;
		if(sum<k)
			li=center+1;
		if(sum==k)
			return center;
	}
	return -1;
}

int main()
{
	fin>>n>>m;
	int i,tip,a,b;
	for(i=1;i<=n;i++)
	{
		fin>>val;
		pos=i;
		update(1,1,n);
	}
	
	for(i=1;i<=m;i++)
	{
		fin>>tip;
		switch(tip)
		{
			case 0:fin>>pos>>val;update(1,1,n);break;
			case 1:fin>>start>>final;sum=0;query(1,1,n);fout<<sum<<'\n';break;
			case 2:fin>>k;fout<<cauta(k)<<'\n';break;
		}
	}
	return 0;
}