#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 start=0;
	for(int step=1<<LogMaxN;step;step>>=1)
	{
		int index=start+step;
		if(index<=N)
		{
			if(x>=aib[index])
			{
				x-=aib[index];
				start=index;
				if(!x)
				{
					return start;
				}
			}
		}
	}
	return -1;
}

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;
}