#include <fstream>

using namespace std;

const char InFile[]="aib.in";
const char OutFile[]="aib.out";
const int MaxN=100111;
const int LogMaxN=17;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,op,x,y,aib[MaxN];

inline int lsb(int x)
{
	return x&-x;
}

inline void update(int x,int val)
{
	for(;x<=N;x+=lsb(x))
	{
		aib[x]+=val;
	}
}

inline int query_sum(int x)
{
	if(x>N)
	{
		return -1;
	}
	int sol=0;
	for(;x;x-=lsb(x))
	{
		sol+=aib[x];
	}
	return sol;
}

inline int query_sum(int x, int y)
{
	return query_sum(y)-query_sum(x-1);
}

inline int query_pos(int x)
{
	int sol=0;
	for(int step=1<<LogMaxN;step;step>>=1)
	{
		int index=sol+step;
		int q=query_sum(index);
		if(q<x && q!=-1)
		{
			sol=index;
		}
	}
	++sol;
	if(query_sum(sol)!=x)
	{
		sol=-1;
	}
	return sol;
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=N;++i)
	{
		fin>>x;
		update(i,x);
	}
	for(register int i=1;i<=M;++i)
	{
		fin>>op;
		if(op==0)
		{
			fin>>x>>y;
			update(x,y);
		}
		else if(op==1)
		{
			fin>>x>>y;
			fout<<query_sum(x,y)<<"\n";
		}
		else if(op==2)
		{
			fin>>x;
			fout<<query_pos(x)<<"\n";
		}
	}
	fin.close();
	fout.close();
	return 0;
}