#include <fstream>
#include <iostream>
#include <cstdlib>
#define N_MAX 100011

using namespace std;

int N;
int Aib[N_MAX];

inline void Update( int xIndex, int& xValue )
{
	for( ; xIndex <= N; xIndex+=xIndex & -xIndex )
		Aib[xIndex]+=xValue;			
}
inline int Query( int a )
{
	int sum=0;
	for( ; a; a-=( a & -a ) )
		sum+=Aib[a];
	return sum;
}
inline int Query2( int a )
{
	int idx, tidx, bitMask=1<<(31-__builtin_clz(N));
	for( idx=0; bitMask ; bitMask>>=1 )
	{
		tidx=idx+bitMask;
		if( tidx <= N )
		{
			if( Aib[tidx] == a )
				return tidx;
			if( a > Aib[tidx] )
			{
				a-=Aib[tidx];
				idx=tidx;
			}
		}
	}
	return -1;
}

int main()
{
	int M, i, x, y, op;
	ifstream in( "aib.in" );
	ofstream out( "aib.out" );
	
	in>>N>>M;
	for( i=1; i <= N; ++i )
	{
		in>>x;
		Update( i, x ); 
	}
	for( ; M; --M )
	{
		in>>op>>x;
		if( 0 == op )
		{
			in>>y;
			Update( x, y );
		}
		else if( 1 == op )
			 {
				 in>>y;
				 out<<( Query(y) - Query(x-1) )<<'\n';
			 }
			 else out<<Query2( x )<<'\n'; 
	}
	
	return EXIT_SUCCESS;
}