#include <fstream>
using namespace std;

ifstream F("aib.in");
ofstream G("aib.out");
#define aib(x) ( ( x^(x-1) ) & x )

typedef int AIB[100011];
int N,M,x,y;
AIB Aib;
int chr;

void update(int pl,int val)
{
	for ( int i=pl;i<=N;i+=aib(i) )
		Aib[i]+=val;
}

int seek(int x)
{
	int rez=0;
	for ( int i=x;i>0;i-=aib(i) )
		rez+=Aib[i];
	return rez;
}

int binfire(int sum)
{
	int st=1,dr=N,mid,x;
    
	while ( dr>st )
	{
        mid=(st+dr) /2;
        x=seek(mid);
        
		if ( x>sum )
			dr=mid-1; 
		else
			if ( x<sum )
				st=mid+1; 
			else 
				return mid;
	}
    
	return ( seek(st)==sum ) ? st : -1 ;
}

int main()
{
	F>>N>>M;
	for (int i=1;i<=N;++i)
		F>>x,update(i,x);
	
	for (int i=1;i<=M;++i)
	{
		F>>chr;
		switch (chr)
		{
			case 0:
				F>>x>>y;
				update(x,y);
				break;
			case 1:
				F>>x>>y;
				G<<seek(y)-seek(x-1)<<'\n';
				break;
			case 2:
				F>>x;
				G<<binfire(x)<<'\n';
				break;
		}
	}
	
	F.close();
	G.close();
	return 0;
}