#include <fstream>
#define NMAX 100100
using namespace std;

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

int A[NMAX], N, M;

void AddAib(int v, int b)
{
	int p = 0;
	while (b <= N)
	{
		A[b] += v;
		while ( !(b & (1 << p)) ) p++;
		b += (1 << p);
		p++;
	}
}
int QueryAib(int a)
{
	int p = 0, s = 0;
	while (a > 0)
	{
		s += A[a];
		while (!(a & (1 << p))) p++;
		a -= (1 << p);
		p++;
	}
	return s;
}
int SearchAib(int val)
{
    int i, step;
    
    for ( step = 1; step < N; step <<= 1 ); 
    
    for( i = 0; step; step >>= 1 )
    {
         if( i + step <= N)
         {
            if( val >= A[i+step] ) 
            {
                i += step, val -= A[i];
                if ( !val ) return i;
            }
         }
    }
    
    return -1;
}
int main()
{
	int i, x, a, b;
	fin >>N >>M;
	
	for (i = 1; i <= N; i++)
		fin >>x, AddAib(x,i);
	for (i = 1; i <= M; i++)
	{
		fin >>x;
		if (x == 0) fin >>a >>b, AddAib(b,a);
		if (x == 1) fin >>a >>b, fout <<QueryAib(b) - QueryAib(a - 1) <<'\n';
		if (x == 2) fin >>a, fout <<SearchAib(a) <<'\n';
	}
	fout.close();
	return 0;
}